常见的时间复杂度按数量级递增,如下:
1)常量级0(1)随着数据规模n增大,对应算法的时间复杂度不变
2)对数级0(logn)随着数据规模n增大,对应算法的时间复杂度成对数曲线logn变化3)线性级0(n)随着数据规模n增大,对应算法的时间复杂度成线性曲线n变化
4)线性对数级0(nlogn)随着数据规模n增大,对应算法的时间复杂度成线性对数曲线nlogn变化
5)平方级0(n^2)随着数据规模n增大,对应算法的时间复杂度成平方级n^2变化6)立方级0(n^3)随着数据规模n增大,对应算法的时间复杂度成立方级n^3变化
7) K此方级0(n^k)随着数据规模n增大,对应算法的时间复杂度成n^k次方级变化
8)指数级0(2^n)随着数据规模n增大,对应算法的时间复杂度成2^n次方级变化
9)阶乘级0(n!)随着数据规模n增大,对应算法的时间复杂度成n!阶乘级变化
常见的空间复杂度按数量级递增,如下:1)常数级0(1)随着数据规模n增大,对应算法的空间复杂度不变
2)线性级0(n)随着数据规模n增大,对应.算法的空间复杂度成线性曲线n变化
3)平方级0(n^2)随着数据规模n增大,对应算法的空间复杂度成立方曲线n^2变化
一段代码的总执行时间=这段代码所有行的执行时间(循环行,可以通过拉平的方式来统计,换言之:所有代码的执行时间与每行代码的执行次数n成正比)
T(n)=O(f(n))
T(n)表示代码执行的时间;
n表示数据规模的大小;
f(n)表示每行代码执行的次数总和。因为它是一个公式,所以用f(n)来表示。
公式中的0,表示代码的执行时间T(n)与f(n)表达式成正比。表示代码的执行时间随数据规模的增长的变化趋势