算法复杂度

1 时间复杂度

以算法中基本操作的重复执行次数作为算法的时间复杂度。一般不必精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可。

1.1 大 O 复杂度表示法

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示
代码执行时间随数据规模增长的变化趋势，所以，也叫作'渐进时间复杂度'
简称'时间复杂度'

当 n 很大时公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了。

1.2 如何分析时间复杂度

大 O 复杂度表示无穷大渐近，因此是一种变化趋势的表现，通常会忽略掉
公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了，因此
分析一个算法、一段代码的时间复杂度的时候，也只关注'循环执行次数最多'的
那一段代码就可以了

1.2.1 数列知识

累加法：递推关系式为an+1−an=f(n)an+1−an=f(n)采用累加法。
累乘法：递推关系式为an+1an=f(n)an+1an=f(n)采用累乘法。
构造法：递推关系式为(1)aa+1=pan+qaa+1=pan+q，(2)aa+1=pan+qnaa+1=pan+qn，都可以通过恒等变形，构造出等差或等比数列，利用等差或等比数列的定义进行解题，其中的构造方法可通过待定系数法来进行。
和化项法：递推公式为Sn=f(n)Sn=f(n)或Sn=f(an)Sn=f(an)一般利用
an={S1，Sn−Sn−1，当n=1当n>=2
an={S1，当n=1Sn−Sn−1，当n>=2
用特征方程求解递推方程（感觉比较生僻，不做解释）
迭代法：从原始递推方程开始，反复将对于递推方程左边的函数用右边的等式代入，直到得到初值，然后将所得的结果进行化简。
例如在调用归并排序mergeSort(a,0,n-1)对数组a[0...n−1]a[0...n−1]排序时，执行时间T(n)T(n)的递推关系式为：
T(n)={O(1)，2T(n2)+O(n)，当n=1当n>=2
T(n)={O(1)，当n=12T(n2)+O(n)，当n>=2

其中，O(n)O(n)为merge()所需要的时间，设为cncn（c为正常量）。因此：
T(n)=2T(n2)+cn=2(2T(n4)+cn2)+cn=22T(n4)+2cn=23T(n8)+3cn=...=2kT(n2k)+kcn=nO(1)+cnlog2n=O(nlog2n),(假设n=2k,则k=log2n)