.. _algorithm:

Algorithm
=========

对数
----

loga^b = x => a^x = b

loga^(mn) = loga^m + loga^n

loga^(m/n) = loga^m - loga^n

loga^(M^n) = nloga^M

loga^b = logc^b / logc^a

ln    e为底
lg    10为底
log    任意底

时间复杂度
----------

渐进时间复杂度，表示数据规模和运算时间之间的关系。

常见时间复杂度从小到大排列:
1. O(1) 常数阶
2. O(logn) 对数阶
3. O(n) 线性阶
4. O(nlogn) 线性对数阶
5. O(n^2) 平方阶
6. O(n^3) 立方阶
7. O(2^n) 指数阶
8. O(n!) 阶乘阶
9. O(n^n) k次方阶

空间复杂度
----------

渐进空间复杂度，表示数据规模和算法存储空间之间的关系。

常见空间复杂度从小到大排列：

1. O(1)
2. O(n)
3. O(n^2)

递归
-----

避免无限递归。

递归条件:

* 一个问题可以分解成几个子问题。
* 问题分解之后，除了数据规模，思路是一样的。
* 存在基线或终止条件。