没有合适的资源?快使用搜索试试~ 我知道了~
数据结构算法时间复杂度的计算.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 80 浏览量
2022-07-11
20:38:15
上传
评论
收藏 38KB DOC 举报
温馨提示
试读
6页
时间复杂度的定义 一般情况下,算法中基本操作重复执行的次数是问题规模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 +
资源推荐
资源详情
资源评论
数据结构算法时间复杂度的计算
时间复杂度的定义
一般情况下,算法中基本操作重复执行的次数是问题规模 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)
资源评论
- m0_626134592023-08-14资源简直太好了,完美解决了当下遇到的难题,这样的资源很难不支持~
是空空呀
- 粉丝: 167
- 资源: 3万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功