时间复杂度的常用符号

1. $\Theta$
   如果 $f(n)=\Theta (g(n))$，则 $f(n)$ 与 $g(n)$ 同阶。（阶是指 $f(n)$ 的指数，比如 $n^2$ 高于 $n$）
2. $O$
   如果 $f(n)=O(g(n))$，则 $f(n)$ 的阶不高于 $g(n)$。
3. $\Omega$
   如果 $f(n)=\Omega (g(n))$，则 $f(n)$ 的阶不低于 $g(n)$。

渐进时间复杂度

定义

程序执行时间随着数据规模的增长关系。

直观的方法

画出函数图像，孰优孰劣一目了然。

对于复杂的

可以直接代入数字。既然 $m,n$ 同阶，可以默认 $m=n$，方便计算。先大概地看一下，B 和 C 都有 $n^2$ 级别，肯定比 A 和 D 大，所以只计算 A 和 D 的。

n      A       D
8      22      32
16     64      80
32     166     192
64     405     448
256    2172    2304
1024   10756   11264

A 更小，考场上建议代完前三个就直接选，$\sqrt{2}\approx 1.4$。（本人去年直接懵了，考完后很崩溃，没过。现在回来重做复盘，感觉这次能过）