Java 数据结构之时间复杂度分析
对于这部分，要牢记一句话：将算法中基本操作的执行次数作为算法时间复杂度的度量。这里所讨论的时间复杂度不是执行完一段程序的总时间，而是其中基本操作的总次数。因此，对一个算法进行时间复杂度分析的要点，无非是明确算法中哪些操作是基本操作，然后计算出基本操作重复执行的次数即可。你总能找到一个 n，可以称为问题的规模，如果处理的数组元素的个数为 n，而基本操作所执行的次数是 n 的一个函数 f(n) (这里的函数是数学中函数的概念)。对于求其基本操作执行的次数，就是求函数 f(n) 。求出以后就可以取出 f(n) 中随 n 增大而增长最快的项，然后将其系数变为 1，作为时间复杂度的度量，记为T(n)=O( f(n)中增长最快的项/此项的系数 )。实际上计算算法的时间复杂度就是给出相应的数量级，当 f(n) 与 n 无关时，时间复杂度 T(n)=O(1)；当 f(n) 与 n 是线性关系时，T(n)=O(n)；当 f(n) 与 n 是二次方关系时，T(n)=O(n²)；以此类推。
通过以上分析，总结出计算一个算法时间复杂度的具体步骤如下：
- 确定算法中的基本操作以及问题的规模。
- 根据基本操作执行情况计算出规模n的函数f(n)，并确定时间复杂度为T(n)=O(f(n)中增长最快的项/此项的系数)。
注意：有的算法中基本操作的执行次数不仅跟初始输入的数据规模有关，还和数据本身有关。例如，一些排序算法，同样有 n 个待处理数据，但数据初始有序性不同，则基本操作的执行次数也不同。一般依照使得基本操作执行次数最多的输入来计算时间复杂度，即将最坏的情况作为算法时间复杂度的度量。
