1、程序（Programs）

算法（Algorithms）+ 数据结构（Data Structure） = 程序（Programs）

2、数据结构和算法的联系

在研究某一类型的数据结构时，总要涉及其上施加的运算。只有通过对所定义运算的研究，才能真正理解数据结构的定义和作用。

3、算法要满足的5个重要特性

（1）有穷性

（2）确定性

（3）可行性

（4）输入

（5）输出

4、评价算法优劣的基本标准

（1）正确性

（2）可读性

（3）健壮性

（4）高效性

5、算法的效率

假设

A计算机能每秒执行百亿条指令

B计算机每秒执行千万条指令

问题：对1000万个数进行排序，谁快？

A 用插入排序大约5.5小时完成，B用归并排序大约20分钟。

由此可以推出，算法（时间复杂度）的选择对任务执行效率的影响，远大于硬件算力的差距。

6、渐进时间复杂度

T(n) = O(n)

随着问题规模n的增大，算法执行时间和增长率f(n)成正比。

程序运行的总时间主要与两点有关：

（1）执行每条语句的耗时

（2）每条语句的执行频率

7、语句频度

简单来说，看执行次数多少判断代码的频度，不看执行时间。

8、计算频度和计算时间复杂度

（1）计算频度

（2）计算时间复杂度

如果n为0：

最好时间复杂度：算法在最好情况下的时间复杂度。

最坏时间复杂度：算法在最坏情况下的时间复杂度。

平均时间复杂度：算法在所有可能的情况下，按照输入实例以等概率出现时，算法计量的加权平均值。

对算法时间复杂度的度量，通常只讨论算法在最坏情况下的时间复杂度，即分析在最坏情况下，算法执行时间的上界。

（3）计算时间复杂度-常量阶示例

如果频度计算出来的值为常数，那么T(n) = O(n)，中O(n)的n值为1。 

（4）计算时间复杂度-一阶示例

（5）计算时间复杂度-平方示例

（6）计算时间复杂度-立方阶示例

立方阶计算方法：

（7）计算时间复杂度-对数阶示例

9、时间复杂度汇总