时间复杂度和空间复杂度

算法的性能可以用时间复杂度和空间复杂度这两个东西来衡量。

时间复杂度 $T (n)$

$T (n)$ 里的T就是Time，这个函数描述了算法在执行时间上和问题规模的关系。一般都是表示执行这个算法，需要运行的基本的语句数量，也就衡量了时间长短。比如 $T (n) = 3 n + 3$ ,表示如果数据的量有n个，程序就要执行 $3 n + 3$ 个语句。

但是这样的表示方法不够本质，不够直观，含有一些无关的信息，为了把算法在时间上本质的特征描述出来，我们使用大O表示法。

大O表示法

$O (f (n))$ 是一个集合。这个集合包含了所有与 $f (n)$ 在 $n \to \infty$ 下比值为常数的所有时间复杂度函数 $T (n)$ 。

也就是说，如果 $l i m_{n \to \infty} \frac{T ( n )}{f ( n )} = C$ （C为常数），那么 $T (n) \in O (f (n)$
有点像等价无穷小哦，不过这里是趋向正无穷。

为表示本质特征， $f (n)$ 只有 $1, lo g_{2} n, n^{k}, 2^{n}, n!, n^{n}$ 等基本函数，作为数量级的表示。

像上面这个 $T (n) = 3 n + 3$ ，很显然 $l i m_{n \to \infty} \frac{T ( n )}{n} = 3$ ,所以它是属于 $O (n)$ 时间复杂度的算法。

所以说到底，你要去看一个算法的时间复杂度，只要去看里面和数据规模n有关的循环（顺序结构的东西只能决定 $T (n)$ 里的常数项），看看执行次数和上面那些基本的函数之间的关系就好了。

两个不同过程前后连接就是两个复杂度相加，你看看哪个量级上更大，保留哪个就好了。循环嵌套就是外面的复杂度乘里面的复杂度，用大O的话两个 $f (n)$ 乘一下就知道新的量级了。本质都是高等数学的极限。

依据高等数学的极限，我们也可以比较出来这几种复杂度的优劣：
$O (1) < O (lo g_{2} n) < O (n) < O (n lo g_{2} n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!) < O (n^{n})$
总体来说我们肯定希望这个时间复杂度越小越好，所以左边的是最好的，右边的是最差的。

但是当数据规模很小的时候，这个规律不一定成立，在隐藏的常数作用下，很可能右边的算法还比左边的好。

最坏、最好、平均时间复杂度

有的时候一个数据量级不能决定到底用多久，可能还和给出的数据序列有关系。比如说这个

cpp

void f(int n, int a[]){
	int i = 0;
	while(a[i] != 114 && i < n){
		i++;
	}
}

假设a里面一定有一个114。顺序的在这个a数组里面找114,找到就结束了。如果这个114在0位置，那执行1个语句就结束了；如果这个114在最后，那光i++就要执行n次。

所以这里有一个最好情况：“114在0位置”，常数级别即结束， $O (1)$ ；有一个最坏情况：“114在最后”， $O (n)$ 。两种情况时间复杂度是不一样的。

平均时间复杂度则是让给出的数据的每一种情况全部都概率相等，算出一个数学期望。比如这里，114在0处概率为 $\frac{1}{n}$ ，在1处概率为 $\frac{1}{n}$ ……那么数学期望就是 $1 \times \frac{1}{n} + 2 \times \frac{1}{n} + \dots + n \times \frac{1}{n} = \frac{n + 1}{2}$ ,最终的平均时间复杂度还是 $O (n)$ 量级的。

一般只看最坏、平均，很少有看最好的。

分支结构

如果分支两边复杂度不一样，取大的那个。

递归

这个可以用递推表达式，看 $T (n)$ 和 $T (n - 1)$ 的关系，用数学归纳法推一下就算出来了。

空间复杂度 $S (n)$

看这个程序运行过程中请求的内存空间大小。同样也用大O，总体原则和上面一样。

程序本身的指令会存入代码段，但这是个常数；程序运行过程中可能会根据数据规模动态地请求不同大小的内存空间，这个就要好好考虑了。比如vector<int> arr(n);这个就是一个空间复杂度 $O (n)$ 量级的。

递归要小心

如果递归次数和数据规模挂钩，那基本上空间复杂度要考虑这个因素了，因为每一次递归都会把当前的变量存入栈内，都是算内存空间的。

时间复杂度T(n)