数据结构与算法邓俊辉——（一）_邓俊辉数据结构

计算：研究对象：规律，技巧；研究目标：高效地计算，低耗。

计算的概念：借助某种工具，按照一定规则，以明确而机械的形式进行。

算法： 输入——待处理的信息（问题）
输出——经处理的信息
正确性——的确可以解决指定的问题
确定性——任意算法可以描述为一个由基本操作组成的序列
可行性
有穷性

好算法：正确、健壮、可读、效率（速度尽可能快，存储空间尽可能少）

评价计算模型总是选择最坏的情况。

大O记号。
O(1):不一定不含循环；
O（logn）:常底数无所谓，常数次幂无所谓。复杂度无限接近于常数；
O（n^c）:从O（n）到O(n²)是编程习题主要覆盖的范围
O（2ⁿ）：这类算法的计算成本增长极快，通常认为是不可忍受的。

复杂度分析的主要方法：1.迭代：级数求和；2.递归：递归跟踪+递推方程；3.猜测+验证

级数：1.算术级数：与末项平方同阶；2.幂方级数：比幂次高出一阶；3.几何级数：与末项同阶；4.收敛级数：O（1）；4.调和级数：h(n)=1+1/2+1/3+…+1/n= O(logn);5.对数级数 log1+log2+…+logn=O(nlogn)

循环与级数的关系：

冒泡排序：在经过k轮扫描交换后，最大的k个元素必然就位。

通过不变性和单调性的分析，从而证明正确性是算法的一个基本技巧和方法。

封底估算【定性方法】

迭代与递归
【减而治之】为求解一个大规模的问题，可以分为两个子问题：其一平凡，另一规模缩减，分别求解子问题。由子问题的解得到原问题的解。
递归跟踪分析：检查每个递归实例累计所需时间（调用语句本身计入对应的子实例），其总和即为算法执行时间。
【分而治之】：为求解一个大规模的问题，可以将其划分为若干（通常两个）子问题，规模大体相当。分别求解子问题，由子问题的解得到原问题的解。

动态规划DFA

递归：在函数定义中调用函数自身的方法

迭代：for循环