1 递推公式法
归并排序的递推公式是：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件： p >= r 不用再继续分解 我们假设对n个元素排序的时间是T(n)，那分解成两个子数组排序的时间是 T ( n 2 ) T(\dfrac{n}{2}) T(2n)。merge函数合并两个子数组的时间复杂度是O(n)。所以归并排序时间复杂度计算公式就是：
T ( n ) = 2 ∗ T ( n 2 ) + n , n > 2 T(n)=2*T(\dfrac{n}{2})+n,n>2 T(n)=2∗T(2n)+n,n>2
T(1)=c;
继续计算T(n)
T(n)=2*T(n/2)+n =2*(2*T(n/4)+n/2)+n=4*T(n/4)+2n =4*(2*T(n/8)+n/4)+2n=8*T(n/8)+3n =8*(2*T(n/16)+n/8)+3n=16*T(n/16)+4n ... =2^k*T(n/2^k)+k*n 当 n / 2 k = 1 n/2^k=1 n/2k=1的时候， k = l o g 2 n k=log_2n k=log2n,代入上面的式子： T ( n ) = c ∗ n + n l o g 2 n T(n)=c*n+nlog_2n T(n)=c∗n+nlog2n,用大O表示法，T(n)=O(nlogn)。
2 递归树法
3 递归树分析法实战
3.1 快排时间复杂度
将k=99，999…替换之后结论相同。
3.2 斐波那契数列
int f(int n) { if (n == 1) return 1; if (n == 2) return 2; return f(n-1) + f(n-2); } 每次分解之后的合并操作只是一次加法，算一个时间1。第一层是f(n-1)+f(n-2)，1次运算；第二层是f(n-2)+f(n-3)，f(n-3)+f(n-4)是两次运算…依次类推，第k层的总耗时是 2 k − 1 2^{k-1} 2k−1。算法总耗时是每层耗时相加。
如果路径长度都为n，那么总耗时是： 2 n − 1 2^n-1 2n−1
1 + 2 + 2 2 + . . . + 2 n − 1 = 2 n − 1 1+2+2^2+…+2^{n-1}=2^n-1 1+2+22+...+2n−1=2n−1
如果路径长度都为 n 2 \dfrac{n}{2} 2n，那么总耗时是 2 n 2 − 1 2^{\dfrac{n}{2}}-1 22n−1
1 + 2 + 2 2 + . . . + 2 n 2 − 1 = 2 n 2 − 1 1+2+2^2+…+2^{\dfrac{n}{2}-1}=2^{\dfrac{n}{2}}-1 1+2+22+...+22n−1=22n−1
所以算法的时间复杂度在 2 n 2 − 1 2^{\dfrac{n}{2}}-1 22n−1和 2 n − 1 2^n-1 2n−1之间。这样的计算不够精确，只是一个范围。但是我们知道了该算法的时间复杂度是指数级的。复杂度非常高。
心得：时间复杂度是可以估算的，不用非常准确。只要数量级保证正确即可。
3.3 全排列的时间复杂度
1 递归公式是
假设数组里的内容是1,2,3.....n f(n)={最后一位是1,f(n-1)}+{最后一位是2,f(n-1)}+...+{最后一位是n,f(n-1)} 4 递归树法分析得步骤
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/202742.html原文链接：https://javaforall.net
