|
|
| 算法的时间复杂度分析主要是分析算法的运行时间，即算法所执行的基本操作数。即使对相同的输入规模，数据分布不相同也决定了算法执行不同的路径，因此所需要的执行时间也不相同。根据不同的输入，将算法的时间复杂度分为3种情况。
|
|
|
| （1）最佳情况。使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。应用最佳情况分析的一个例子是已经证明基于比较的排序算法的时间复杂度下限为Ω(nlgn)，那么就不需要白费力气去想方设法将该类算法改进为线性时间复杂度。
|
|
|
| （2）最坏情况。使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，它提供了一个保障，情况不会比这更糟糕。另外，对于某些算法来说，最坏情况还是相当频繁的。而且大致上看，平均情况通常与最坏情况的时间复杂度一样。
|
|
|
| （3）平均情况。算法的平均运行时间。一般来说，这种情况很难分析。举个简单的例子，现要排序10个不同的整数，输入就有10!种不同的情况，平均情况的时间复杂度要考虑每一种输入及其该输入的概率。平均情况分析可以按以下3个步骤进行。
|
|
|
|
|
|
|
|
|
|
|
|
|
| 式中，pi为第i类输入发生的概率；ti为第i类输入的执行时间，输入分为m类。
|
|
|
|
|
|
|
|
|
|
|
| （3）Θ记号。给出一个函数的渐进上界和下界，即渐进确界。
|
|
|
|
|
| 从算法的结构上看，算法可以分为非递归形式和递归形式。非递归算法的时间复杂度分析较简单，本小节主要讨论递归算法的时间复杂度分析方法。
|
|
|
| （1）展开法。将递归式中等式右边的项根据递归式进行替换，称为展开。展开后的项被再次展开，如此下去，直至得到一个求和表达式及其结果。
|
|
|
| （2）代换法。这一名称来源于当归纳假设用较小值时，用所猜测的值代替函数的解。用代换法解递归式时需要两个步骤：猜测解的形式；用数学归纳法找出使解真正有效的常数。
|
|
|
| （3）递归树法。递归树法弥补了代换法猜测困难的缺点，它适于提供"好"的猜测，然后用代换法证明。在递归树中，每一个节点都代表递归函数调用集合中每一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加得到递归式所有层次的总代价。当用递归式表示分治算法的时间复杂度时，递归树的方法尤其有用。
|
|
|
| （4）主方法。也称为主定理，给出求解以下形式的递归式的快速方法，即
|
|
|
|
|
| 式中，a≥1和b>1是常数；f(n)是一个渐进的正函数。
|
|
|
