[toc]

常见时间复杂度

执行次数函数举例              阶                       非正式术语
12                                      O(1)                     常数阶

2n + 3                                O(n)                     线性阶

3n^2 + 2n + 1                    O(n^2)                  平方阶

5log2n + 20                       O(logn)                 对数阶

2n + 3nlog2n + 19             O(nlog)                 nlogn阶

6n^3 + 2n^2 + 3n +4          O(n^3)                  立方阶

2^n                                     O(2^n)                  指数阶

注意, 经常将 log2n ( 以 2 为底的对数 ) 简写成 logn

常见时间复杂之间的关系

所消耗的时间从小到大

O(1) < O(logn) < O(n) < O(nlog) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)