算法时间复杂度分析

网友投稿 772 2022-09-06

算法时间复杂度分析

算法时间复杂度分析

1、时间复杂度分析

只关注循环执行次数最多的一段代码总复杂度等于最高阶项的复杂度嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

推导大O阶:

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中,只保留最高阶项3、如果最高阶项存在且不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

常见的时间复杂度

常数阶

线性阶

平方阶

对数阶

线性对数阶

立方阶

指数阶

阶乘阶

O(1)

O(n)

O(n*n)

O(logn)

O(nlogn)

O(n的立方)

O(2的n次方)

O(n!)

从小到大依次是: O(1) < O(logn) < O(n) < O(nlogn) < O(n*n)< O(n的立方) < O(2的n次方) < O(n!)

2、空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:SQL Server 面面观——数据库对象
下一篇:Vue学习之--------Scoped样式(2022/8/1)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~