常用排序算法的时间和空间复杂度及算法时间复杂度的简单计算详解程序员
学会简单的求解算法的时间复杂度也是很有必要的,接下来看看如何简单的计算是时间复杂度:
求解算法的时间复杂度的具体步骤是:
⑴ 找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:
for (i=1; i i++)
x++;
for (i=1; i i++)
for (j=1; j j++)
x++;
第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
常见的算法时间复杂度由小到大依次为:
一个示例:
(1) int num1, num2;
(2) for(int i=0; i i++){
(3) num1 += 1;
(4) for(int j=1; j j*=2){
(5) num2 += num1;
(6) }
(7) }
分析:
1.
语句int num1, num2;的频度为1;
语句i=0;的频度为1;
语句i i++; num1+=1; j=1; 的频度为n;
语句j j*=2; num2+=num1;的频度为n*log2n;
T(n) = 2 + 4n + 3n*log2n
2.
忽略掉T(n)中的常量、低次幂和最高次幂的系数
f(n) = n*log2n
3.
lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n)
= 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3
当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0
所以极限等于3。
T(n) = O(n*log2n)
原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/7289.html
服务器部署程序员系统优化网站设置运维相关文章
- Keyman算法设计哲学
- 8个常见的机器学习算法的计算复杂度总结
- 最长上升子序列 LIS算法实现[通俗易懂]
- Z—score模型公式计算_Prim算法
- 【大厂高频算法题】反转链表
- redis系列之——一致性hash算法「建议收藏」
- Shamir密钥分享算法简析
- 文本相似度计算_文本相似度分析算法
- 隐私计算-Oblivious Transfer算法理论研究与实践
- 「 【Cent OS8】centos启用谷歌bbr网络拥塞算法 」
- React源码分析4-深度理解diff算法5
- BP神经网络(反向传播算法原理、推导过程、计算步骤)
- 【数据挖掘】神经网络 后向传播算法 向前传播输入 案例计算分析 ( 网络拓扑 | 输入层计算 | 隐藏层计算 | 输出层计算 )
- 【计算机网络】网络层 : RIP 协议 ( 路由选择协议分类 | RIP 协议简介 | 信息交换 | 距离向量算法 | 计算示例 )★
- 【计算理论】计算复杂性 ( 算法复杂度标记 | 渐进上界 | 大 O 记号 | 常用的渐进上界 )
- 【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )
- 【算法】刷题范围建议 和 代码规范
- 一种求离散数学传递闭包的算法java实现详解编程语言
- java学习深度优先算法详解编程语言
- 日历查询的算法如何计算某一天是星期几
- C#计算两个文件的相对目录算法的实例代码
- python算法学习之计数排序实例
- JavaScript实现的一个计算数字步数的算法分享