对时间复杂度还是不太了解...

august · 发表于 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)呢?

corivsky · 发表于 2008-11-26 13:50:34

常数系数可以忽略。

。。。。貌似

tkokof · 发表于 2008-12-3 17:04:41

你可以将大O符号看作一种数量级别的标志，
那么2*（nu+tu）与nu+tu就在一个数量级别上，
所以常数就能省略了。（具体的可以参看一些算法方面的书籍：））

august · 发表于 2008-12-4 10:35:01

那有没有什么很好的算法方面的书籍介绍介绍.

tkokof · 发表于 2008-12-6 11:46:38

Robert Sedgewick写的《An Introduction to the Analysis of Algorithms 》（《算法导论》）
另外的国外学者所写的一些算法教材也都不错（如《算法引论》，《算法设计》，《算发设计与分析》等等）
（国内的就鲜有佳者了。。。）
//
//
另外不得不再介绍一本：Knuth写的《The Art of Computer Programming》（《计算机程序设计艺术》）
有机会试着看看吧，绝对经典，但深度。。。

dbshy · 发表于 2009-2-12 12:27:33

常数可以忽略，比如O twon = On because N>> two
还有复杂度可以看数据结构,也有将，但比较简单

		自动登录	找回密码
密码			立即注册

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