时间复杂度的分类和理解

3.分类

按数量级递增排列，常见的时间复杂度有：

常数阶O(1), 注意：1仅仅表示常数的意思；

对数阶O(log2n),

线性阶O(n),

线性对数阶O(nlog2n),

平方阶O(n²)，

立方阶O(n³),...，

k次方阶O(n^k),

指数阶O(2ⁿ) 。

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

4.关于对其的理解

《数据结构（C语言版）》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比。"

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O( f(n) )

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。