方法2：递归树做复杂度分析
递归的思想是将大问题分解成小问题处理，大问题的处理逻辑与小问题的处理逻辑一致。其分解过程可以被表示成一棵树结构，这棵树被称为递归树。
递归树在我们分析时间复杂度的时候很有用，通常它与O(logn)时间复杂度有关。举个例子（下面的递归树都是自上而下数层数的），归并排序
f(n)
/ \
f(n/2) f(n/2)
/ \ / \
f(n/4)f(n/4) f(n/4) f(n/4)
......
f(1) ......每次将数据平均分成两份，直到只有一个元素为止。每次分解后的都需要n次循环进行合并，对于f(n)，需要时间为n，对于f(n/2)需要的时间为n/2，而对与整个f(n/2)所在的第二层，其总的时间为n/2 × 2 = n，依此类推，可以得出，每一层的所需时间都是n，那总的所需时间就是n × h，h是树的高度。
那么我们需要知道h是多少。我们知道 2^h = n，则h=logn（以2为底）
则总的时间复杂度就是O(nlogn)。
递归树做复杂度分析大致都这个思路。
快排的时间复杂度分析
假设每次分区左分支数据规模与右分支数据规模的比值是1：k，则递归树如下
f(n)
/ \
f(n/(k+1))f(nk/(k+1))
......
f(1) ......第二层， n/(k+1) + nk/(k+1) = n，依此类推每一层总的都需要n次循环进行分区。则所需时间依然是n × h。
对于最短路径，h = logn（以k+1为底），对于最长路径，h = logn（以 (k+1) / k 为底）。k越大h越接近n，所以分区元素的选择很重要。
所以总的时间复杂度依然是O(nlogn)。
斐波那契数列的时间复杂度分析
[[方法1：递归（Recursion）]]里面有一个爬楼梯的例子，说每次只能走1个或者2个台阶，问n阶的楼梯有多少种爬法。
其实是一个斐波那契数列：
/**
* 递归解法
* @return
*/
public int recursion(int n){
if(n<1){
return 0;
}
// 只有一个台阶的时候只有一种解法
if(n==1) return 1;
// 只有两个台阶的有两种解法（走一次两个台阶、走两次一个台阶）
if(n==2) return 2;
// 走n个台阶有两种走法，走一步和走两步。所以n阶的走法就是走n-1台阶和走n-2台阶的和。
return recursion(n-1)+recursion(n-2);
}
其递归树如下：
f(n)
/ \
f(n-1) f(n-2)
/ \ / \
f(n-2)f(n-3) f(n-3) f(n-4)
......
f(1) ......对于最长路径，每次减1，其h=n，对于最短路径，每次减2，其h >= n/2。
每次递归后加法的时间记为1，则第一层时间为1，第二层时间为2，第三层为4，第h层时间为2^(h-1)，则总的时间复杂度为:
1 + ..... + 2^(h-1) = 2^h - 1又因为 n >= h >= n/2
所以最坏时间复杂度是2^n ，最好时间复杂度是2^(n/2)。则时间复杂度是O(2^n)，指数级别。
全排列的时间复杂度
全排列问题如下:
给定一个不含重复数字的数组 `nums` ，返回其 _所有可能的全排列_ 。你可以 **按任意顺序** 返回答案。
**示例 1：**
**输入：**nums = [1,2,3]
**输出：**[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
**示例 2：**
**输入：**nums = [0,1]
**输出：**[[0,1],[1,0]]
**示例 3：**
**输入：**nums = [1]
**输出：**[[1]]
**提示：**
- `1 <= nums.length <= 6`
- `-10 <= nums[i] <= 10`
- `nums` 中的所有整数 **互不相同**思路是，如果我们确定了第一位数据，那就变成了求解剩下 n−1 个数据的排列问题。而第一位数据可以是 n 个数据中的任意一个，因此它的取值就有 n 种情况。所以，“n 个数据的排列”问题，就可以分解成 n 个“n−1 个数据的排列”的子问题。
假设数组中存储的是1，2， 3...n。
f(1,2,...n) = {第一位是1, f(n-1)} + {第二位是2, f(n-1)} +...+{第一位是n, f(n-1)}。过程如下
- 如果只有一个元素直接返回单个元素的的排列结果
- 遍历数组nums，将当前index元素与首位元素start交换位置
- 对余下的从start+1开始的子数组进行全排列
- 组合首位元素与子数组全排列的结果，将index元素与首位元素start复原
package cn.lishiyuan.leetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
* 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
*
* * * 示例 1：
*
* 输入：nums = [1,2,3]
* 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
* 示例 2：
*
* 输入：nums = [0,1]
* 输出：[[0,1],[1,0]]
* 示例 3：
*
* 输入：nums = [1]
* 输出：[[1]]
* * * 提示：
*
* 1 <= nums.length <= 6 * -10 <= nums[i] <= 10 * nums 中的所有整数 互不相同
*/
public class LeetCode46 {
public static <T> List<List<T>> resolve(T[] nums) {
List<List<T>> permutations = permutations(nums, 0);
return permutations;
}
/**
* 递归解决全排列
* @param nums
* @param start
* @return
* @param <T>
*/
private static <T> List<List<T>> permutations(T[]nums,int start){
List<List<T>> res = new ArrayList<>();
if(start == nums.length - 1){
res.add(Collections.singletonList(nums[start]));
return res;
}
for(int i = start;i < nums.length;i++){
// 当前元素为首位的全排列结果
List<List<T>> list = new ArrayList<>();
// 将i 与 start交换位置，剩下的start - 1进行全排列
T temp = nums[i];
nums[i] = nums[start];
nums[start] = temp;
List<List<T>> permutations = permutations(nums, start + 1);
for (List<T> permutation : permutations) {
// 组合全排列结果
List<T> c = new ArrayList<>();
c.add(nums[start]);
c.addAll(permutation);
list.add(c);
}
res.addAll(list);
// 交换回去
nums[start] = nums[i];
nums[i] = temp;
}
return res;
}
}复杂度分析：
f(n)
|
f(n-1)……f(n-1)
|
f(n-2)……f(n-2)
.
.
.
f(1)……f(1)对于第一层，需要循环n次进行数据交换；对于第二层，每次需要n-1次循环进行数据交换，一共n次，于是第二层共需要n ×（n-1）次交换，那么依此类推，最后一层需要n×(n-1)×(n-2)×…×1次交换，于是总的时间复杂度就是：
n + n×(n-1) + …… + (n×(n-1)×(n-2)×…×1)时间复杂度是介于O(n!)与O(n × n!)，也就是说是一个阶乘规模的时间复杂度，复杂度非常高。