算法复杂度

---

一、时间规模的直觉

事件	时间	量级
宇宙大爆炸至今	~138 亿年	$10^{21}$ sec = $10\times (10^{10}{)}^2$
“三生三世”	~300 年	$10^{10}$ sec
100 年		$3\times 10^9$ sec
1 天	24 小时	$10^5$ sec

---

二、复杂度层级

类型	记号	说明
常数	$O(1)$	与输入规模无关
对数	$O(\log n)$	见下方换底/幂次性质
线性	$O(n)$
幂	$O(n^c)$
指数	$O(a^n)$	不可忍受

对数复杂度的两个性质

换底公式：${\log }_{a}n={\log }_{a}b\cdot {\log }_{b}n$，其中 ${\log }_{a}b$ 是常数，所以对数底数在 $O$ 记号中无所谓

幂次法则：$\log (n^c)=c\cdot \log n$，其中 $c$ 是常数，所以 $O(\log n^c)=O(\log n)$

---

三、等比级数求和实例

$$T(n)=O(1)\cdot (2^0+2^1+2^2+\cdots +2^{\log n})=O(1)\cdot (2^{\log n+1}-1)=O(n)$$

理解

等比级数 $1+2+4+\cdots +n$ 的和约为 $2n$，所以整体复杂度还是 $O(n)$，不会因为逐层倍增而”爆炸”。