幻想森林

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2548|回复: 5

[通用编程] 对时间复杂度还是不太了解...

[复制链接]

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
发表于 2008-11-26 12:04:55 | 显示全部楼层 |阅读模式
nu,tu代表某个值
int i,j;
for(i=1;i <=nu;++i)
//做某事
;
for(j=1;j <=tu;++j)
//做某事
;
for(i=1;i <=nu;++i)
//做某事
;
for(j=1;j <=tu;++j)
//做某事
;
这样四个循环,那它的时间复杂度为什么不是 O(2*(nu+tu)) 呢?
而是是O(nu+tu)呢?
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复

使用道具 举报

13

主题

80

帖子

1198

积分

⑥精研

积分
1198
发表于 2008-11-26 13:50:34 | 显示全部楼层
常数系数可以忽略。

。。。。貌似
回复 支持 反对

使用道具 举报

0

主题

2

帖子

16

积分

②入门

积分
16
发表于 2008-12-3 17:04:41 | 显示全部楼层
你可以将大O符号看作一种数量级别的标志,
那么2*(nu+tu)与nu+tu就在一个数量级别上,
所以常数就能省略了。(具体的可以参看一些算法方面的书籍:))
回复 支持 反对

使用道具 举报

313

主题

1574

帖子

1万

积分

⑧专业

*永恒国度*

积分
14145
QQ
 楼主| 发表于 2008-12-4 10:35:01 | 显示全部楼层
那有没有什么很好的算法方面的书籍介绍介绍.
[img][/img] http://shop33698673.taobao.com被别人嫉妒,证明你优秀,嫉妒别人说明你无能
回复 支持 反对

使用道具 举报

0

主题

2

帖子

16

积分

②入门

积分
16
发表于 2008-12-6 11:46:38 | 显示全部楼层
Robert Sedgewick写的《An Introduction to the Analysis of Algorithms 》(《算法导论》)
另外的国外学者所写的一些算法教材也都不错(如《算法引论》,《算法设计》,《算发设计与分析 》等等)
(国内的就鲜有佳者了。。。)
//
//
另外不得不再介绍一本:Knuth写的《The Art of Computer Programming》(《计算机程序设计艺术》)
有机会试着看看吧,绝对经典,但深度。。。
回复 支持 反对

使用道具 举报

3

主题

7

帖子

73

积分

②入门

积分
73
发表于 2009-2-12 12:27:33 | 显示全部楼层
常数可以忽略,比如O twon = On because N>> two
还有复杂度可以看数据结构,也有将,但比较简单
没有力量也是一种罪过
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|幻想森林

GMT+8, 2024-3-29 09:36 , Processed in 0.020869 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表