数据结构算法时间复杂度计算行业资料_第1页
数据结构算法时间复杂度计算行业资料_第2页
数据结构算法时间复杂度计算行业资料_第3页
数据结构算法时间复杂度计算行业资料_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1/1数据结构算法时间复杂度计算-行业资料

文档来源为:从网络收集整理.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)intnum1,num2;

(2)for(inti=0;in;i++){

(3)num1+=1;

(4)for(intj=1;j=n;j*=2){

(5)num2+=num1;

(6)}

(7)}

分析：

1.

语句intnum1,num2;的频度为1；

语句i=0;的频度为1；

语句in;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的指数”。

人人文库> 全部分类> 教育资料 > 辅导培训

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论