数据结构算法时间复杂度的计算
更新时间:2023-03-28 21:20:01 阅读量: 行业资料 文档下载
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
时间复杂度的定义
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O 是数量级的符号),简称时间复杂度。
根据定义,可以归纳出基本的计算步骤
1. 计算出基本操作的执行次数T(n)
基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。
2. 计算出T(n)的数量级
求T(n)的数量级,只要将T(n)进行如下一些操作:
忽略常量、低次幂和最高次幂的系数
令f(n)=T(n)的数量级。
3. 用大O来表示时间复杂度
当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。
一个示例:
(1) int num1, num2;
(2) for(int i=0; i<n; i++){
(3) num1 += 1;
(4) for(int j=1; j<=n; j*=2){
(5) num2 += num1;
(6) }
(7) }
分析:
1.
语句int num1, num2;的频度为1;
语句i=0;的频度为1;
语句i<n; i++; num1+=1; j=1; 的频度为n;
语句j<=n; 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)
1
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
= 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3
当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0
所以极限等于3。
T(n) = O(n*log2n)
简化的计算步骤
再来分析一下,可以看出,决定算法复杂度的是执行次数最多的语句,这里是num2 += num1,一般也是最内循环的语句。
并且,通常将求解极限是否为常量也省略掉?
于是,以上步骤可以简化为:
1. 找到执行次数最多的语句
2. 计算语句执行次数的数量级
3. 用大O来表示结果
继续以上述算法为例,进行分析:
1.
执行次数最多的语句为num2 += num1
2.
T(n) = n*log2n
f(n) = n*log2n
3.
// lim(T(n)/f(n)) = 1
T(n) = O(n*log2n)
--------------------------------------------------------------------------------
一些补充说明
最坏时间复杂度
算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的运行时间不会比任何更长。
求数量级
即求对数值(log),默认底数为10,简单来说就是“一个数用标准科学计数法表示后,10的指数”。例如,5000=5x10 3 (log5000=3) ,数量级为3。另外,一个未知数的数量级为其最接近的数量级,即最大可能的数量级。
求极限的技巧
2
正在阅读:
数据结构算法时间复杂度的计算03-28
表白的话真实点的浪漫--表白话语02-08
简述我国电子商务发展的历程12-23
2020年最新转观念勇担当创效益专题讨论发言稿精选三篇09-10
小学阶段所学破折号的作用09-16
新农村建设的感想与体会01-05
家常素菜100道05-19
快速破解语病题的二十三种方法03-15
- 北京第二外国语学院翻硕考研辅导班优劣比较
- 银行存款余额调节表模板
- 防电信诈骗知识
- 国际海运货运术语
- 北师大四年级语文下册第三单元基础过关练习
- 安全生产的心得体会
- 2012宁夏回族自治区事业单位招聘考试公共基础知识包过题库
- 水文地球化学习题
- 翻译目的论研究综述
- 2018年医药行业风险分析报告
- 用6-9的乘法口诀求商
- 乡镇经济发展及招商引资工作开展情况汇报(总结)
- 入党积极分子考察表模板
- 课间十分钟阅读练习
- 信息安全与信息道德
- 2014陕西社区工作者考试专业知识:社区基础大纲之社区建设
- 婚姻法司法解释三(最新)
- 抗原抗体结合的影响因素
- 北师大版四年级语文上册《月光曲》公开课课件
- 中职学生职业道德教育现状成因分析及新途径
- 复杂度
- 数据结构
- 算法
- 时间
- 计算