| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1538 人关注过本帖
标题:[求助]关于时间复杂度
只看楼主 加入收藏
freeboy517
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2005-12-10
收藏
 问题点数:0 回复次数:5 
[求助]关于时间复杂度

关于时间复杂度,自学数据结构以来除了一些简单的循环,其他的根本就找不到思路,请问大家对此问题的方法

搜索更多相关主题的帖子: 时间 数据结构 思路 根本 
2006-03-10 14:28
qzt040613
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:63
专家分:0
注 册:2006-3-15
收藏
得分:0 
时间复杂度是频度的量级,求复杂度时最好先求一下频度。

天地无极,我本逍遥!
2006-03-18 13:20
freeboy517
Rank: 1
等 级:新手上路
帖 子:11
专家分:0
注 册:2005-12-10
收藏
得分:0 

那请问一下,频度是怎样的,能举个例子吗?谢谢了


2006-03-21 10:31
windqiu56
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2006-3-14
收藏
得分:0 

关于时间复杂度个人学习的策略:
1.理解书本基本的概念(尤其是语句的频度)
2.会分析循环语句的执行所满足的条件,从而确定循环次数(一般是问题规模n的函数)
3.了解常用的数量级(如:O(1),O(n),O(n^2),O(n^3)…………O(lgn)等增长关系比较)
当然了,仅知道上面还不能见题能解!需要你有一定的数学素质(数列,指对方程,不等式会经常成为出题的目标)。如果你数学狂差的话,要好好补补了!(哈哈!!本人是数学系出生的(优势了))
下面举两例加以说明,望朋友们慢慢体会喽
例1.分析下列算法段的时间频度及时间复杂度 ______________数列方法的运用
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for ( k=1;k<=j;k++)
x=i+j-k;
分析:i=1时,j=1;k=1 ; (循环1次)
i=2时,j=1;k=1 循环1次; j=2,k=1 循环1次 ; j=2;k=2 循环1次 (共循环1+2次)
i=3时,j=1,k=1 循环1次; j=2,k=1 循环1次 ; j=2,k=2 循环1次
j=3;k=1 , 2 ,3 循环3次 (共循环1+2+3次)
…………
…………
i=n时,……(归纳可得:共循环1+2+3+……+n = n(n+1) / 2 次)
所以,语句“ x=i+j-k”在整个循环中一共执行次数为(1)+(1+2)+(1+2+3)+(1+2+3+4)+……(n(n+1) / 2 )=n/6(n+1)(2n+1)=O(n^3)
(其中用到对等差数列的前n项和的和数列再求和的拆项技巧;体现了对数学的要求)

例2.下程序中带划线的语句的执行次数的数量级( O( log2(n) ) ) _____指数不等式的运用
i=1;
WHILE i<n DO
i=i*2

分析:此题循环条件是:i<n ,而i的值每循环一次就是原来的2倍;
但循环的次数不像上例那样好归纳;故可设循环次数(频度)为T(n)
i的值每循环一次就是原来的2倍可得不等式
2^T(n)<n
得T(n)<log2(n)
取最大值有数量级O( log2(n) )

通过以上的分析,可见数据结构的学习需要一个好的数学功底!!
以上仅代表个人意见,勿以语言攻击!!
谢谢阅读!!望交流
只希望学到更多的东西!


[此贴子已经被作者于2006-3-21 12:33:39编辑过]


2006-03-21 12:27
wuqiang080
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2006-4-6
收藏
得分:0 
好,谢谢!懂了
2006-04-06 23:01
独角龙
Rank: 1
等 级:新手上路
帖 子:221
专家分:0
注 册:2006-5-5
收藏
得分:0 

谢谢啦.有点思路了!


奋斗改变一切!!
2006-05-08 19:02
快速回复:[求助]关于时间复杂度
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024883 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved