【学习随记】时间空间复杂度

时间复杂度

常用的时间复杂度有7种：

1. 常数时间复杂度；$O(1)$\
2. 对数时间复杂度；$O(\log n)$\
3. 线性时间复杂度；$O(n)$\
4. 平方时间复杂度；$O(n^2)$\
5. 立方时间复杂度；$O(n^3)$\
6. 指数时间复杂度；$O(2^n)$\
7. 阶乘时间复杂度；$O(n!)$

注：从上到下时间复杂度越来越大
常规的时间复杂度都容易分析，麻烦的是递归，遇到递归时一般需要把状态树画出来。比如说代码是：

int fib(n){
	if(n<2)	return n;
	return fib(n-1) + fib(n-2)
}

当输入为6时，状态树为：

结果是$O(2^n)$，分析就很麻烦。

对于递归，常见的情况有4种

1. 二分查找\
     在有序数列中查找目标数，每次查找都一分为二，最后时间复杂度是$O(\log n)$。\
2. 二叉树遍历\
    虽然每次也都一分为二，但每边都已相同的时间复杂度继续下去，或者说，二叉树每个节点都且仅遍历一次，所以时间复杂度是$O(n)$。比如二叉树的前，中，后序遍历，都是线性复杂度。\
3. 有序的二维矩阵查找\
     时间复杂度是$O(n)$。\
4. 归并排序\
     时间复杂度是$O(n\log n)$

关于具体的数学推导的话参看链接: 数学推导

关于主定理的话，参看这个：主定理

空间复杂度

这个就比时间复杂度善良很多，一般就考虑两种情况：

1. 新开数组的长度\
2. 递归的深度
   若递归里新开数组，我们就考虑大的那个复杂度就行。