算法时间复杂度

1. 简介

算法的时间复杂度是指在问题规模为 $N$ 时整个算法执行的基本语句单元次数，记为 $T(N)$ 。

2. 分类

在算法时间复杂度分析中，常用 $\log-\log \ plot$ 图去衡量算法时间复杂度，该图横坐标为 $\log N$（$N$ 为问题规模），纵坐标为 $\log T$（$T$ 为时间频度）。

• exponential：指数复杂度
• cubic：$N^3$
• quadratic：$N^2$
• linearithmic：$N\log N$
• linear：$N$
• logarithmic：$\log N$
• constant：$C$

3. 符号

以 $N\log N$ 为例：

• $\Theta(N \log N)$：表示时间复杂度渐近为 $N \log N$ 。

• $O(N \log N)$：表示时间复杂度小于等于 $N \log N$ 。

• $\Omega(N \log N)$：表示时间复杂度大于等于 $N \log N$ 。