算法基础1

常见的时间复杂度按数量级递增,如下:

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)表达式成正比。表示代码的执行时间随数据规模的增长的变化趋势

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容