加载中…
个人资料
N_O_I_P
N_O_I_P
  • 博客等级:
  • 博客积分:0
  • 博客访问:87,636
  • 关注人气:6
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

时间复杂度,提高组的鸡肋

(2018-10-05 10:11:35)
分类: 知识点
这是2016年选择中的一題,时间复杂度的计算。对于普及组来说,它的难度在可控之内,但是如果出现下面这类題目,很难找到保证,偏偏它的分值又不高!

2016年提高组

答案是C
这題的形式已经符合时间复杂度总定论的形式:T(n)=aT(n/b)+f(n);
2016年提高组
它是定个对比式:(f(n)=sqrt(n))  vs (n^logb^a )=n^(log4^2)=sqrt(n),符合第二个式;
所以T(n)=O(sqrt(n)*log n)形态,就是这样来的。

其中的多项式大于指,设g(n)渐进大于f(n),则存在数c>0和n0,使得对于任意 n >= n0 有 c*g(n) >= f(n).
多项式大于定义如下:
存在常数c>0,c1>0,c2>0,使得
c1 * f(n) * n ^ c <= g(n) <= c2*f(n)*n^c

f(x)多项式大于g(x):存在实数e>0,使得f(x)>g(x)*n^e
f(x)多项式小于g(x):   存在实数e>0,使得f(x)
“多项式大于”是一个不容易判定的问題。

如果不是从总定理,递推式就是递归树,从f(1)……f(n)的累加;
这样就形成了两项和,一般只能直观地看,两项式那项缩减快就忽略它;然后计算另一项是多大值。
所以这題就形成了 右项式是sqrt(n)*n;
左项式就递推:t(1)=1; t(4)=2: t(16)=4,t(64)=8,t(n/4)中作整除计算,然后求其累加通项式
得数是什么?似乎有点复杂了。得数x的关系是∑(2^(n-3)) <  x <∑(2^n),不容易对比出两者的大小;
这也是总定理的意思,可以减少对比的计算量。这类題型,还是用总定理处理吧。

T(n)=O(n)+4T(n/2) , n^(log4^2)=n^2 ,f(n)=O(n)   n^((loga^b)=2),符合第一个判别式,因此,T(n)=O(n^2)
又如
T(n)=9T(n/3)+n 同样因为log9^3==2,所以答案是O(n^2)
T(n)=T(2n/3)+n,因为log(3/2)^1==0 (任何实数的0次方==1),所以答案应该是O(n);
假如是
T(n)=T(2n/3)+1,因为log(3/2)^1==0 (f(n)==1)),是第二种情况,以答案应该是O(lgn);

但是
T(N)=2T(N/2)+NlogN就出麻烦了,因为不符合总定理的要求。这道題其实是算法导到4-6.2证明題。
拿到这里来考,有点过分。
T(N)=2T(N/2)+NlogN
因为log2^2==1,因为n^1 < nlgn,看上去符合总定理。一般在考试中就会选择总定理,得出nlogn。实际情况是,因为f(n)=nlgn渐近大于n^(logb^a)=n,却不 是多项多大于。对于任意的正实数e,比值f(n)/n^(logb^a)在这道題中等于(nlgn)/n=lgn,渐迫小于n^e,所以不符合总定理的要 求。需要使用递归树。T(N/2)=2T(N/4)+NlogN   如此类推,T(N)=2^(logN)*T(1)+N*logN*logN,所以是O
N*logN*logN。
习题所证是:
对于T(n)=aT(n/b)+f(n),f(n)=(n^(logb^a))*((lgn)^k),时间复杂度是
(n^(logb^a))×(lgn)^(k+1);
所以,因为log2^2==1,k=1,答案就是n*lgn*lgn
例如:
归并排序的总时间T(n)=2T(n/2)+o(n),套用此公式,就是O(nlogn)


时间复杂度计算这里,基本上就是整个NOIP中,计算难度最高,但分值又最低的“鸡肋”。与其攻此难点,还不如扫描一下常用的答案,以及符合主定理的主要情型,会做简单一点的递归计算,也就算了。
不然时间花得太多。
详细参考算法导论page47-page64页


简单总结一下:
1)最可靠的办法,还是采用递归树,按递推展开的办法寻解。这在普及组的題目中,递推会比较简单,因此可控;但是在总定理不适用的环节,(判断总定理真的不适用,是另一个坑),递推展开之后,要找到它的通项表达又将是另一个挑战,本身就是一条复杂数列同类型高难级别的奥数題。然后还需要用对数知识加以转化。
2)能够直接套用总定理的话,当然是简单的,还可能再出现。(毕竟去年才出现了一次)。只不过,它受到判断“多项式大于”条件的影响,要完成这个判断,把握性并不大。
3)要完全精通这个环节,(它属于研究生计算机专业二年时侯的课程),就需要把算法导到这几十页全钻透!对于初中生来说,太过分,对于高中生来说,时间消耗太大。而得分却只是……1.5分!

所以这个环节的准备,最好是了解它的原理后,多看几个T(n)表达式对应的O结果。把它当奥数題去办好了。


0

阅读 收藏 转载 喜欢 打印举报/Report
前一篇:2016年提高组
后一篇:2015年提高组
  

新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

新浪公司 版权所有