Re: [理工] 演算法求時間複雜度

看板Grad-ProbAsk作者kiki86151 (白飯)時間12年前 (2013/11/09 23:03)推噓2(2推 0噓 7→)

留言9則, 4人參與討論串2/2 (看更多)

另開板先解釋這題一下這題是變化題不能用master也不是調和數列原PO已經用遞迴樹種出來是n*Σi=1~logn 1/(i^2)了至於Σ1/(i^2)等於Θ(?) 其實證明跟調和數列很像調和數列怎麼證的?Σi=1~n 1/(i) 也就是黎曼和積分簡單來說n越大時就越接近某區域面積證調和數列利用∫(上底n 下底1)1/x dx 最後就會證出Θ(logn) 方便標誌上底n 下底1= 1_n 我直接忽略上黎曼(上限)和下梨曼(下限)簡單證就好同理 Σ1/(i^2) 利用∫1_n 1/x^2 dx =-1/x | 1_n = 1-(1/n) =(n-1)/n=Θ(1) 此題我用展開再展一次好了 T(n)=2T(n/2)+ n/(lgn)^2 =2( 2T(n/4)+ (n/2) / (lg(n/2))^2 ) + n/(lgn)^2 =4T(n/4)+ n/(lgn)^2 + n/(lg(n/2))^2 歸納得 2^k T(n/2^k) + n* [ 1/(lgn^2) + 1/(lg(n/2)^2)+.....+1/(lg(n/2^(k-1)) ] 令n=2^k (k=lgn) 使得T(n/2^k)=T(1)=c(常數) 因此得 n*c+ n * [ 1/lgn^2 + 1/((lgn-2)^2) + ..... + 1/1^2 ] 最後整理得 T(n)=n*c+ n * Σi=1~logn 1/(i^2) (P.S 要注意的地方它是1到lgn 所以積分上底不是n 是lgn!! 也就是∫1_lgn 1/x^2 dx = lgn-1/lgn 雖然還是Θ(1)) 所以T(n)=n*c + n*Θ(1) = Θ(n) ) 為什麼要注意的呢同樣類變化題T(n)=2T(n/2)+ n/(lgn) 展開最後才是調和數列1/1+1/2+....1/lgn 上底是lgn 因為∫1_lgn 1/x dx = lglgn-1 = Θ(lglgn) 所以此題是Θ(n*lglgn) (展開或離散都可以解出來@@ 甚至樹上面那題離散不太好解==) 至於為什麼有些狀況不能用master 隨便舉例好了T(n)=2T(n/2)+ n*lgn loga_b=1 D大你覺得 n和nlgn 後者growth order>前者為什麼不是T(n)=Θ(n*lgn) 而是by case2 T(n)=Θ(n*lgn*lgn) 同樣T(n)=2T(n/2)+ lgn n和lgn 且前者growth order>後者但卻是 Θ(lgn*lgn) (以上舉例通通可以用展開或離散解可以去證證看) 我是認為master的精神感覺是離散的轉換法總結可是在判斷loga_b時遇到比較特別的f(n) 要稍微注意一下因為很多case 有些master遇到變化f(n)很容易出錯反而離散和展開最可靠(雖然離散遇到機車的題目會很麻煩= =) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.231.45.156

推

DoubleFish

11/10 08:55, , 1^F

11/10 08:55, 1^F

推

woody3724

11/10 13:42, , 2^F

11/10 13:42, 2^F

→

jurt

11/11 16:18, , 3^F

11/11 16:18, 3^F