算法时间复杂度

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。