主题：关于时间复杂度和空间复杂度的疑惑?!!!!!!!!!!!!!!!!!!!
jxx321
[专家分：240] 发布于 2006-01-27 11:59:00
我对数据结构中的那个时间复杂度和空间复杂度很不理解.不知道到底应该怎么算.
那位朋友能帮我解说下呀.帮帮我这位新手吧.
[em1][em1][em1][em1][em1][em1]
我在书上看到这段话很不明白>
人们通常采用大O表示法来描述算法分析结果。如果存在正的常数M和n0，当问题的规模n>=n0后，算法的时间量度T(n)=<M*f(n),那么就称该算法的时间复杂度为0(f(n)).这种说法意味着：当n充分大时，该算法的时间复杂度不大于f(n)的一个常数倍。
这里的O和n,n0 T(n) M,等等.这些到底什么意思呀?
回复列表 （共6个回复）
沙发
wanggcc [专家分：1450] 发布于 2006-01-26 13:50:00
有不明白的问题可以去百度查查
板凳
jxx321 [专家分：240] 发布于 2006-01-26 14:03:00
我也查过了呀!
可以都和书上讲的差不多.很难理解.
3 楼
rickone [专家分：15390] 发布于 2006-01-30 02:42:00
我觉得这个定义有点问题，我举个例子，比如T(n)=2n，那么我们可以取f(n)=n,M=2,n0=1这很显然，但是我们也可以取f(n)=n*n,M=1,n0=2，那时间复杂度到底是O(n)还是O(n*n)呢？
实际上当时我看到这些的时候，我完全是按我学的数学里的大O理解的，在数学里大O是表示同阶的意思，也就是同阶无穷大。
在数学里，如果T(n)=O(f(n))，那么当且仅当
limT(n)/f(n)=C C为非零常数
n->无穷大
比如
lim 2n/n = 2
n->无穷大
因此2n=O(n)
反过来也对，n=O(2n)，2n=O(2n)
但是一般在算法分析里都把大O里面化得简单，也就是取‘主要部分’，呈现‘主要部分’，以此把握它的增长趋势。
比如，如果T(n)=2n*n-3n，显然是O(n*n)，随着n的增大，T(n)中的2n*n部分会成‘主要部分’，到n非常大的时候，-3n的影响可以忽略。
总而言之，T(n)是一个随n增大无限增大的数列，即无穷大，而大O描述就是找到它的‘阶’，因为T(n)的阶如果是k，当且仅当T(n)=O(n^k)。
4 楼
rickone [专家分：15390] 发布于 2006-01-30 02:47:00
此外，为什么要用大O的形式描述，为什么不用阶描述，也挺方便，XX算法是多少阶的算法。。。，是因为有时候不能用阶完全描述，比如O(nlogn),O(n!),O(2^n)等等，
6 楼
rickone [专家分：15390] 发布于 2006-06-10 16:58:00
又翻了些资料,那个定义是正确的,比如我如果T(n)=n,那可以是O(n)也可以是O(n*n),按定义是正确的,而所有的大O表示中最小的那个(最精确的)是另外一个符号,大O里面一个'工',表示确切的时间复杂度,我们经常谈论到的是后者.
我来回复
您所在位置：