算法复杂度

递归和迭代

递归比迭代更加耗费内存空间，因为函数的上下文数据都存储在栈空间中，直到函数返回才被释放。

递归比迭代更加耗费时间，因为递归调用函数会有额外的开销。

如果函数递归调用为尾递归，则经过编译器、解释器优化可以在空间效率上和迭代差不多。

尾递归：return 递归函数，即返回递归的函数。

O(1)

运行时间/空间不随输入变化而变化。

O(n)

以线性级别增长。eg：单层循环，循环长度与输入数据有关。

O(n²)

以平方级别增长。eg：多层循环，循环长度与输入数据有关。

O(2^n)

以指数级别增长。eg：类似于"细胞分裂"，一个函数体内运行同样的两个函数（递归）。

O(logN)

以对数级别增长。eg：类似于"每次循环缩减到上次的一半"，分治。

O(nlogN)

以线性对数级别增长。eg：线性和指数级别的组合，快速排序、归并排序。

O(n!)

以阶乘级别增长。eg：全排列。