深入理解时间复杂度
2022/7/3 23:22:05
本文主要是介绍深入理解时间复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
时间复杂度 O(f(n))
算法需要执行基本运算的次数的
级别。
一,思考
目前个人认为:时间复杂度实际就是考量两种情况。
1. 循环 for(),while()
2. 递归
二,何为n
理论上指:问题规模。
拆开来说,就是for(),while()循环了n次,递归了多少次(递归的情况略微复杂)。
三,何为f(n)
算法执行基本运算的次数【基本运算(加减乘除)】
1. 举个例子
例一
int a , b = 0;//用于交换的临时变量 for(int i=0;i<n;i++){ // for循环共执行了n次 a += b; //执行"a += b"一次 }
所以 f(n)= n * 1 = n。
例二
int a , b = 0;//用于交换的临时变量 for(int i=0;i<n;i++){ // for循环共执行了n次 a += b;//执行"a += b"一次 a += b;//执行"a += b"一次 }
所以 f(n)= n * (1 + 1)= 2n。
2. 总结
在复杂的程序也是这样计算f(n)。
四,什么是大O
我自己的理解:就是带有具体意义(耗费时间的程度)评级,就像 甲乙丙丁戊己庚辛壬癸。
1.时间复杂度概念理解
a. 概念下的时间复杂度
大O用来表示上界的,这里的上界是极限的概念,即n -> ∞,当用它作为算法的最坏情况运行时间的上界.例如:图中的 插排,快排的最坏情况的时间复杂度。
b.实际面试情况下的说的时间复杂度
就是我们平时说的平均时间复杂度。
2.算法时间复杂的的排序
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶
O(logn)中的log是以什么为底?
结论:我们统一说 logn,也就是忽略底数的描述。
证:假如有两个算法的时间复杂度,分别是log以2为底n的对数和log以10为底n的对数。
3.总结
- 数据用例的不一样,时间复杂度也是不同的,理论上的数据用例是无穷大,而实际上可能是有限的数据用例,抛开数据规模谈复杂度就是耍流氓。
五.时间复杂度的计算(数据规模无穷大)
1. 求出f(n)
一行一行的去求,把结果加起来即可。
2. 化简f(n)
假设 f(n) = 2n^2 + 10n + 1000
首先 去掉加法常数项: f(n) = 2n^2 + 10n
然后 去掉常数系数 f(n) = n^2 + n
最后 去掉 低阶的项 f(n) = n^2 。
【也可以用提取n,然后去掉加法常数项的思路:f(n) = n*(n + 1)-> f(n) = n^2】
参考书目
《代码随想录》《算法笔记》 《数据结构与算法》
这篇关于深入理解时间复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?