Re: [理工] 资料结构

楼主: gsmzxcvbnm   2016-03-22 20:26:37
※ 引述《gsmzxcvbnm ()》之铭言:
: 洪逸的资料结构某题答案与其它本不同, 洪逸的版本我也看不太懂
: 洪逸
: http://i.imgur.com/9A0xbL0.jpg
: 高点
: http://i.imgur.com/E66FgFz.jpg
我还是不知道n-ki=1是怎么来的耶,n-ki应该是第k项吧?那怎么会等于1?
所以效能是把所有k加起来?我完全不懂啊
而且我一开始的想法是
x=n-1
x=n-2
x=n-3
.
.
.
.
x=n-n
T(n)=n^2-(n+1)n/2=O(n^2)
这样想好像很白痴
作者: OppOops (Oops)   2016-03-22 23:51:00
精确来说应该是 当x = n - ki = c, 为第k个while loop其中 0 < c < i(那个说明是在讲第k+1个loop时, x<=0)后面再对 i = 1...n,个别状况加总想成T(n) = t(1) + t(2) + ... + t(i) + ... + t(n)t(i) 即为 k次 loop的时间, 又 k = (n-c)/i , 答案可求
楼主: gsmzxcvbnm   2016-03-23 08:21:00
嗯嗯,谢谢

Links booklink

Contact Us: admin [ a t ] ucptt.com