数据结构与算法 1-3 最坏时间复杂度与计算规则
数据结构与算法 1-3 最坏时间复杂度与计算规则
本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍算法时间复杂度的三种不同程度：最坏时间复杂度、最优时间复杂度以及平均时间复杂度，并且介绍几种时间复杂度的基本计算规则。
一
最坏时间复杂度
算法的本质就是解决问题的思路，而对于不同类型规模的数据来说，解决问题的思路可能相同，但是算法最终执行的基本操作数可能是不同的。下面通过排序算法来说明：
比如：
- 对于一个无序序列[3, 5, 1, 8, 2, 9, 12]，通过某种排序算法A将其变成一个从小到大的有序序列[1, 2, 3, 5, 8, 9, 12]。假设此时排序算法A将前面无序序列变成有序序列需要执行n^2个基本操作（n为序列中运算个数），相当于算法中有两层嵌套循环；
- 对于一个有序序列[1, 2, 3, 4, 5, 6, 7]，通过排序算法A对有序序列进行排序，由于此时的输入数据是一个有序序列，因此排序算法A只需要扫描一遍，看序列中的元素是否有序，有序的话只需要遍历一遍即可。相当于执行：for i in list一层循环。此时对于这个有序序列操作数变成了n。
通过上面的分析也可以发现，对于同样的算法来说，输入数据不同，可能会影响最终的操作数。也就是说对于不同输入数据，同样一个算法的效率可能不相同。对应于排序算法而言：
- 处理有序序列的情况下，算法效率最高称为最优时间复杂度；
- 处理序列中每个元素都无序的情况下，算法的效率最低称为最坏时间复杂度；
- 还有一种称之为平均时间复杂度，是最优时间复杂度与最坏时间复杂度的平均。
总的来说，分析算法时，存在几种可能的考虑：
- 算法完成工作最小需要多少基本操作，即最优时间复杂度；
- 算法完成工作最多需要多少基本操作，即最坏时间复杂度；
- 算法完成工作平均需要多少基本操作，即平均时间复杂度。
也就是对于算法时间复杂度还有三个程度的概念。
- 对于最优时间复杂度来说，其价值不大，因为他没有提供什么有用信息，其反映的只是最乐观最理想的情况，没有参考价值。比如某个排序算法对于一个有序的序列执行100个基本操作，但是如果这个排序算法在处理无序序列的时候并不能够在100个基本操作内解决排序任务，因此对于最优时间复杂度没有太大的意义；
- 对于最坏时间复杂度，提供了一种保证，表明算法在此种程度的基本操作中一定能完成工作。比如在最坏情况下，需要执行100^2个基本操作，也就是说在100^2个基本操作之内肯定能够把所有问题解决，此时的最坏时间复杂度是一种保证，保证在此程度下的基本操作内一定能够完成任务工作；
- 对于平均时间复杂度，是对算法的一个全面评价，因此它完整全面的反映了这个算法的性质。但另一方面，这种衡量并没有保证，不是每个计算都能在这个基本操作内完成。而且，对于平均情况的计算，也会因为应用算法的实例分布可能并不均匀而难以计算。
我们主要关注算法的最坏情况，亦即最坏时间复杂度。
二
时间复杂度的几条基本计算规则
程序的流程控制有基本操作、顺序结构、循环结构以及分支结构。相应四种程序流程控制在大O表示法下的时间复杂度计算如下：
(1)基本操作，即只有常数项，认为其时间复杂度为O(1)；
(2)顺序结构，时间复杂度按加法进行计算；
(3)循环结构，时间复杂度按乘法进行计算；
(4)分支结构，时间复杂度取最大值；
相应的还有两条时间复杂度的基本计算规则：
(5)判断一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略；
(6)在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。
下面通过前面介绍的算法为例，通过上面的计算规则分析算法时间复杂度：
计算时间复杂度（最坏时间复杂度）的步骤：
- 时间复杂度通过T(n)来表示，总的基本操作数使用F(n)表示，此时n代表程序当中的1000，此时将两个1000都换成n，表示问题的规模；
- 第一行代码是循环，他决定了他的循环体执行多少次，也就是第2行到第6行，此时F(n) = n；
- 第二行还是循环，这个循环仍然执行n次，此时F(n) = n * n；
- 第三行代表的是一个基本步骤，此时F(n) = n * n * 1；
- 第三行和第四行是顺序结构，由(2)可知时间复杂度通过加法来计算，第四行是分支结构，一支进入条件体另一支直接退出，由(4)可知，选择分支中时间复杂度最大的值作为分支结构的时间复杂度，此时if分支：
- 一支执行print输出，执行1个基本操作数；
- 另一支直接退出程序，执行0个基本操作数。
因此F(n) = n * n * (1 + max(1, 0)) = n ^ 2 * 2，根据(5)将次要项和常数项去掉，最终算法的时间复杂度为T(n) = O(n ^ 2)。
