递归树

递归树

递归的思想，将大问题分解为小问题来求解，然后再将小问题分解为小小问题。这样一层一层的分解，直到问题的数据规模被分解得足够小，不用继续递归分解为止。
如果把这个一层一层分解过程画成图，它其实就是一棵树—递归树。

归并的时间复杂度、快排的最好情况时间复杂度适合用递推公式分析。
快排平均时间复杂度适合用递归树分析。
二叉树的前中后序遍历都不适合。

归并排序的时间复杂度

归并排序每次会将数据规模一分为二。因为每次分解都是一分为二，所以代价很低，把时间上的消耗记作常量l。归并算法中比较耗时的是归并操作，也就是把连个子数组合并为大数组。每一层归并操作消耗的时间总和是一样的，跟要排序的数据规模有关，把每一层归并操作消耗的时间记作n。

只需要知道这棵树的高度h，用高度h乘以每一层的时间消耗n，就可以得到总的时间复杂度O(n*h)。
归并排序递归树是一棵满二叉树，满二叉树的高度大约是log₂n，归并排序的时间复杂度就是O(nlogn)。

快速排序的时间复杂度

递推公式分析时间复杂度

快速排序在最好情况下，每次分区都能一分为二，此时用递推公式T(n)=2T(n/2)+n，推导出时间复杂度是O(nlogn)。

平均情况下，每次分区之后，两个分区的大小比例为1:k。当k=9时，如果用递推公式的方法求解时间复杂度，递推公式为T(n)=T(n/10)+T(9n/10)+n。

递归树分析时间复杂度

快速排序的过程中，每次分区都要遍历待分区区间的所有数据，每一层分区操作所遍历的数据的个数之和就是n。只要求出递归树的高度h，快排过程遍历的数据个数就是h*n，时间复杂度就是O(h*n)。

每次分区并不是均匀的一分为二，递归树并不是满二叉树。
快速排序结束的条件是排序的小区间大小为1，即叶子节点里的数据规模是1。从根节点n到叶子节点1，递归树中最短的一个路径每次都乘以1/10，最长的一个路径每次都乘以9/10。计算后可得，从根节点到叶子节点的最短路径是log₁₀n，最长路径是log_10/9n。
遍历数据的个数总和就介于nlog₁₀n和nlog_10/9n之间。根据复杂度的大O表示法，对数复杂度的底数不管是多少，统一写成logn。所以当分区大小比例是1:9时，快速排序的时间复杂度仍然是O(nlogn)。

只要k的值不随n变化，是一个事先确定的常量，快排的时间复杂度就是O(nlogn)。

斐波那契数列的时间复杂度

递推公式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，第三层的总时间消耗是2²。依次类推，第k层的时间消耗就是2^k-1，整个算法的总时间消耗就是每一层时间消耗之和。

如果路径长度都为n，总和就是2ⁿ-1。
如果路径长度都是n/2，那总和是2^n/2-1。
所以算法的时间复杂度介于O(2ⁿ)和O(2^n/2)之间。指数级。

全排列的时间复杂度

把n个数据的所有排列都找出来，就是全排列的问题。
可以用递归来打印一组数据的所有排列。

如果确定了最后一位数据，就变成求解剩下n-1个数据的排列问题。最后一个数据可以是n个数据中的任意一个，它的取值有n种情况。“n个数据的排列”问题，可以分解成n个“n-1个数据的排列”的子问题。

递推公式：
f(1,2,…n) = {最后一位是1, f(n-1)} + {最后一位是2, f(n-1)} +…+{最后一位是n, f(n-1)}

全排列

public void printPermutations(int[] data, int n, int 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 tmp = data[i];
        data[i] = data[k-1];
        
        printPermutations(data, n, k-1);

        tmp = data[i];
        data[i] = data[k-1];
        data[k-1] = tmp;
    }
}

画出递归树
第一层分解有n次交换操作，第二层有n个节点，每个节点分解需要n-1次交换，所以第二层总的交换次数是n(n-1)。第三层有n(n-1)个节点，每个节点分解需要n-2次，所以第三层总的交换次数是n(n-1)(n-2)。

以此类推，第k层总的交换次数就是n(n-1)(n-2)…(n-k+1)。最后一层的交换次数就是n*(n-1)*(n-2)*…*2*1。每一层的交换次数之和就是总的交换次数。

n + n*(n-1) + n*(n-1)*(n-2) +… + n*(n-1)(n-2)*…*2*1

最后一个数等于n!，前面n-1个数都小于最后一个数，总和肯定小于n*n!。全排列的递归算法的时间复杂度在O(n!)与O(n*n!)之间。