关于算法优劣的一个问题,请大哥们给与解决,谢!
有时为了比较两个同数量级算法的优略,须突出主项的常数因子,而将低次项用大"O"记号表示.如:设T1(n)=1.39nlgn+100n+256=1.39nlgn+0(n),T2(n)=2.0nlgn-2n=2.0nlgn+0(n),这两个式子表示,当n足够大时T1(n)优于T2(n),因为前者的常数因子小于后者.请用此方法表示下列函数,并指出当N足够大时,哪一个较优,哪一个较劣?
1/ T1(n)=5n*n-3n+60lgn,
2/ T2(n)=3n*n+1000n+31lgn
3/ T3(n)=8n*n+3lgn
4/ T4(n)=1.5n*n+6000nlgn
/*其中lgn=以2为底的logn*/
此题为数据结构一道练习题,哪位朋友有答案,和计算过程,请告知!邮件,论坛都可以
znfo@163.net
问题点数：50、回复次数：5Top
1 楼liupanwin（永不吹）回复于 2002-09-05 17:23:48 得分 10
通常平方级别肯定大于lgn,故我的答案为
3>1>2>4Top
2 楼darkstar21cn（≮天残≯无畏)(死亡进行时）回复于 2002-09-05 17:35:53 得分 10
n*n>n>log(n)
但是按照数据结构中的时间复杂度来说，这几个都是一样的时间复杂度（o(N*N))。它只比较数量级，而不比较你所说的系数。Top
3 楼Lawrence444（胖子）回复于 2002-09-05 18:28:34 得分 10
全都一样。
没说的。Top
4 楼alidiedie（阿里）回复于 2002-09-05 19:36:01 得分 10
胖子说的没错,一样,但按楼主的定义,复杂度应该是:
1.5n*n+O(lgn)
2.3n*n+O(lgn)
3.8n*n+O(lgn)
4.1.5n*n+O(lgn)
n较大时,孰优孰劣,一看便知.Top
5 楼o3y（想飞的菜鸟）回复于 2002-09-06 08:03:20 得分 10
按楼主的题意应该是3>1>2>4，不过实际上这几个算法在一个数量级的话应该没什么差别。Top
