有些同学可能会很困惑：时间复杂度的表示怎么一会儿是 大O, 一会儿是(读作Omega)，一会儿又是（读作Theta）？
这三个符号略有区别，要用数学语言才能描述，略显枯燥，我们到后面再聊大O、、表示时间复杂度的区别，大家先记住，大O、（Omega）、(Theta)都是表示时间复杂度的3种渐进符号；总的来说 ，大O是小于等于， 是大于等于；是等于。
目录
大O、、表示时间复杂度的区别
渐近分析asymptotic analysis:
上界：big O notation
下界: big Omega notation
代换法
递归树求时间复杂度
归并排序递归树
wndxgz递归树
快速排序递归树
全排列的时间复杂度
主定理
Insertion Sort；Sort A[1,..,n]# 插入排序的伪代码；eg. A= [8,2,4,9,3,6]# 由于第2个元素是2，把2移到8前面：2,8,4,9,3,6； 再看第3个元素4，得到2,4,8,9,3,6，一直循环下去；for j <- 2 to n: do key <- A[j] # 构造一个数组A,其中元素从2到j是已经排序好的有序部分； i <- j-1 # 内循环从 j-1 减到0 while i > 0 and A[i] > key: do A[i+1] <- A[i] i <- i-1 A[i+1] <- key
插入排序的时间复杂度分析；
最坏: 数组A是逆序的， (等差数列，算术级数）
对于n很小时，插入排序较快，当n很大时不快。
大O、、表示时间复杂度的区别
大O、（Omega）、(Theta)都是表示时间复杂度的3种渐进符号；总的来说 ，大O是小于等于， 是大于等于；是等于。
算法的运行时间取决于输入数据的规模n；把时间复杂度看作n的函数；定义T(n)为输入规模为n时的最长运行时间。
渐近分析asymptotic analysis:不考虑代码运行时具体的硬件环境；关注运行时间随着数据规模的增长幅度。用忽略低阶项和常数系数的渐近符号表示。
上界：big O notation定义为：存在适当的常数 使得 对所有成立, 假设非负；也就是 可看作一个函数集合 ，存在适当的常数 使得以的常数倍为上界；
比如 就表示去掉首项系数2和低阶项之后剩下的小于等于。eg 。
注：这里大O前面的等号不是对称的，我们不能由推出。
eg. 表示的函数集中存在某个函数 ，使得;可看作误差项。
下界: big Omega notation表示存在常数 使得 对所有成立，也就是当n足够大时，有大于等于的某个常数倍；
比如; 也就是渐近地大于 lgn。
【capital theta】是大于等于且小于等于； o 【little o】是严格小于； 【little omega】是严格大于。
求解递归式的方法有3种：代换法【substitution method】；递归树【recursion tree】
代换法先猜测解的形式，再用数学归纳法验证，再求解常数项。也就是求出具体的满足上述定义的 来。
eg已知递归式 ，
我们先猜测;也就是假设对所有有; 通过数学归纳【Induction】有 ;要保证余项，所以当时，不等式恒成立。
证明：假设对所有都成立；则 当时才有;所以不成立。
改进Induction hypothesis : 假设对所有有 ; 则;要证明;则余项；所以。也就是当时成立， 是常数，所以要大于；也就是要足够大。
递归树求时间复杂度形如 的递归树可以用后面讲到的主方法、主定理求解。递归思想:是将大问题分解为小问题来求解，然后再将小问题分解为更小的问题。这样一层一层地分解，直到问题规模被分解得足够小，不用继续递归分解为止。这种方法不太严谨；有待证明；通常用递归树找出答案，再用代换法来验证。
归并排序递归树 #归并排序伪代码merge_sort A[1,...,n]1. if n =1 ,done,2. 对A[1,...,ceil(n/2)] 和A[ceil(n/2)+1 ,...,n]递归调用归并排序；其中ceil(n/2)是对n/2取上限3. 把第2 步得到的两个排序完的表合并。关键在于第3 步的merge，假设有2个排序好的数组 [2,7,13,20] 和[1,9,11,12]；由于两个数组都是有序的，所以只需要比较两个数组的第一个元素，找出最小的那个并写到最终的数组中，再把指针向后移一，再比较剩下的两个数组中的元素谁最小；所以先把 1写入到数组中再去掉1 （或者指针后移），由于每次只比较两个元素（和数组元素的数目无关），有【1,2,7,9,11,12,20】所以第3 步的时间为2n for n total elements.
对于归并排序的时间复杂度有：
其中第三步的时间复杂度为;第二部由于把数组从中间位置一分为二再归并，所以为；所以n大于1 的情形，T（n）就等于第2、3步的时间相加。
先来考虑归并排序的这种情形，由于隐式函数和cn都是一阶的，我们用cn代替： ；其中c为大于0 的常数；每次分解都是一分为二，我们把时间上消耗记叙常量O(1). 把它写成递归树，就相当于是对归并排序算法第2、3步的逐步二分 次，直到最后都为叶子节点【时间复杂度为O(1)】。归并排序递归树的构造方法如下图；
现在只需要知道这棵树的高度h，用高度h 乘以每一层的时间消耗n，就可以得到总的时间复杂度O(n*h)。由于归并排序是一棵满二叉树，那h = log2n ,再由于之前讲过的的【对数阶的复杂度可以通过换底公式相互转换，所以用lg表示对数阶】 所以粗略估计的归并排序的时间复杂度就是O(nlogn)。
由上图可以看出，每一层的运行时间都是cn,叶子层的时间为.所以总的运行时间为 .在渐近情况下比要快。所以当输入规模n足够大时，归并排序要优于插入排序。
wndxgz递归树再以一棵wndxgz数列【1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...；它的第n项可写作F(n)=F(n-1)+F(n-2)】的递归树为例，节点的数字表示数据的规模，一个节点的求解可以分解为左右子节点两个问题的求解。
f(n) 分解为f(n - 1) 和 f(n-2)，每次数据规模都是-1或者-2，叶子节点的数据规模是1或者2。所以，从根节点到叶子节点，每条路径长度是不一样的。如果每次都是-1，那最长的路径大约是n；如果每次都是 -2，那最短路径大约就是 n/2。每次分解之后的合并操作只需要一次加法运算，我们把这次加法运算的时间消耗记作1; 从上往下，第一层总时间消耗是 1，第二层总时间消耗是 2，第三层的总时间消耗就是4，依次类推，第k+1 层的时间消耗就是2^k。如果路径长度为n，那这个总全就是 2^n -1。 如果路径长度都是 n/2，那整个算法的总时间消耗就是2^(n/2) -1。所以，这个算法的时间复杂度就介于O(2n)和O(2n)/4之间。
快速排序递归树在最好情况下，快速排序每次分区都能一分为二，这个时候用递推公式 T(n) = 2T(n/2) + n，很容易就能推导出时间复杂度是O(nlogn)。假设平均情况下，每次分区之后，两个分区的大小比例为 1：k。当 k =9 时，如果用递推公式的方法来求解时间复杂度的话，递推公式就写成 T(n) = T(n/10) + T(9n/10) + n。把递归分解的过程画成递归树得到下图。
快速排序的每次分区都要遍历待分区区间的所有数据，所以每一层分区操作遍历的数据个数之和就是n。只要求出递归的高度h，就可以得出快排过程的时间复杂度O(hn)。快速排序结束的条件是待排序的小区间大小为1。从根节点n 到叶子节点1，递归树中最短的一个路径是每次都乘以 1/10，最长的路径是每次都乘以9/10。根据复杂度大O表示法，对数复杂度的底数不管是多少，我们统一写成logn，所有当大小比例是1：9时，快速排序的时间复杂度仍然是O(nlogn)。
全排列的时间复杂度全排列问题: 如何把n 个数据( 1，2，3...n)的所有排列都找出来.。如何借助递归树，分析出这个代码的时间复杂度。
/**假设数组中存储的是 1，2，3...n。*f(1,2,3...n) = {最后一位是1，f(n - 1)} + {最后一位是2，f(n - 1)} + ...+ {最后一位是n，f(n - 1)} */public void pringPermutations(int[] data, int n, int k) {// n 表示数组大小，k表示要处理的子数组的数据个数if (k == 1) {for (int i = 0; i < n; i++) {System.out.print(data[i] + " ");}System.out.println();}for(int i = 0; i < k; ++i) {int tem = data[i];data[i] = data[k-1];data[k-1] = tem;pringPermutations(data, n, k-1);tem = data[i];data[i] = data[k-1];data[k-1] = tem;}}第一层分解有n次交换操作，第二层有n 个节点，每个节点分解需要 n-1 次交换，所以第二层的交换次数是n*(n-1)，同理，第三层交换次数就是n*(n-1)(n-2)。各层交换次数总合就是 n + n(n-1) + n*(n-1)(n-2) +… +n! 。也就是说全排列的递归算法的时间复杂度大于O(n!)，小于O(nn!)。
主定理前面我们只是列举了一部分递归树求解时间复杂度的方法，但是更广泛的诀窍是用Master method，它虽然限制很多但是应用超级方便，
它只适用于形如的递归式中：有a个子问题；每个子问题的数据规模是n/b；还要满足, f(n)要是渐近趋正（asympotically positive）的，这类递归树的画法规则为：
(1)每个节点的分支数为a；
(2) 每层的节点为T(n) = aT(n / b) + f(n)中的f(n)在当前的n/b下的值。
(3)每层的右侧标出当前层中所有节点的和。
下面的主定理给出3种case：
case2在算法导论课中又写作 ：存在某个 ； 使得 ；则 有下式成立;
.
对于case3中 表示下一层的所有值之和。
例题 : 下面的4个递推式的f(n)不同导致的时间复杂度也不同。
【1】
由于 属于case1， , 所以有
【2】
由于 属于case2， , 所以有
【3】
由于 属于case3， , 所以有
【4】 【不适用master method 】则 .
参考资料：
【1】主定理与递归树计算算法时间复杂度
【2】递归树： 如何借助树来求解递归算法的时间复杂度