一、概念

O表示法：

设T( n)和 g( n)是正整数集到正实数集上的函数。

称T( n) = O( g( n)) ，当且仅当存在一个正常数 C 和 n0，使得对任意

的 n ≥ n0，有T( n) ≤ C g( n)。

其中：n 是算法输入的规模，如数组的长度，图的顶点数等；

一个算法时间复杂性是O(g( n))，称其时间复杂性的阶为g( n)；

大 O 符号定义了函数 T(n) 的一个 上限 ，算法 的运行 时间（基本运算

次数）至多是g(n)的一个常数倍。

即： T(n)的增长速度至多与

g(n)的增长速度一样快。

二、常见时间复杂度

在每秒处理1亿次左右基本操作的计算机上，可以处理的1s对应的数据量量级：

O(n)：10^7到10^8之间

O(nlogn):10^5到10^6

O(n^2)：10^3到10^4

O(n^3)：10^2到10^3

O(2^n)：20到30

O(n!)：10到12

三、 常用性质

（1）常系数，低次项以及低阶可忽略

（2）对数底可忽略

根据换底公式：

即时间复杂度的阶与对数底无关

以任何数为底的，都可以是O(logn)

（3）对数常数次幂可忽略

四、常用结果

（1）调和级数——O(logn)

（2）级数