王道_数据结构 1.2_2_算法的时间复杂度

一、为什么要事先预估算法时间开销

事后统计算法运行时间无法排除与算法本身无关的外界因素；
如：机器性能、编程语言、机器指令质量以及有些算法不能事后统计。

二、时间复杂度的计算与技巧

1、化简“算法时间开销”的计算方式的依据

完整列出算法运行时间的表达式之后，我们可以发现，当问题规模n趋于无穷大时：
（1) 可以只考虑阶数高的部分；
（2）此部分常数项系数可以忽略

2、常用技巧

（1）加法、乘法规则

加法规则：多项相加，只保留最高阶的项，且系数变为1。
乘法规则：多项相乘，都保留。

（2）时间复杂度的数量级阶数排行

“常对幂指阶”

3、计算时间复杂度的结论与步骤

（1）结论

1、顺序执行的代码（不在循环体内的语句）只会影响常数项，可以忽略
2、只需挑选循环中的一个基本操作分析他的执行次数与n的关系即可
3、如果有多层嵌套循环，只需关注最深层循环循环了几次

（2）步骤

1、找到一个基本操作（最深层循环）
2、分析该基本操作的执行次数x与问题规模n的关系x=f（n）
3、x的数量级O（x）就是算法时间复杂度T（n）

4、两个小练习

步骤：
列出循环执行次数x与问题规模n的关系；
解出x=？n

四、三种时间复杂度

我们一般只研究算法的最坏时间复杂度和平均时间复杂度

五、总结（思维导图）

• 为什么研究的都是规模n趋于无穷大的情况，因为算法的性能问题只有在n很大时才会暴露出来。