promotion image of download ymail app
Promoted

一題時間複雜度小疑問(遞迴)

T(n) = 2T(n/2) + (n-1)

=4T(n/4) + (n-2) + (n-1)

=8T(n/8) + (n-4) + (n-2) + (n-1)

=...........

=nT(1)+... //這邊有點卡住

這是Merge Sort的時間複雜度的遞迴式

我知道可以用Master Theorem,求出O(n log n)

但上面解法,請問我錯在哪?

我最後那邊卡住不太知道怎麼跑

感謝各位

1 個解答

評分
  • sponge
    Lv 6
    7 年前
    最佳解答

    您的解並沒有錯,只是沒有抓到它的一般形式

    =2T(n/2) + (n-1)

    =4T(n/4) + (n-2) + (n-1)

    =8T(n/8) + (n-4) + (n-2) + (n-1)

    能整理出:

    =2^k T(n/2^k) + Σ(n-2^i), i = 0 ~ k-1

    k=1, k=2, k=3 就是這三條等式的一般化

    所以最後要代入 k=log2(n) 來展開Σ

    Σ(n-2^i), i = 0 ~ k-1

    =n*k - Σ(2^i)

    =n*k - ( 1+2+4+...+2^(k-1) )

    =n*k - (2^k - 1)

    =n*log2(n) - (n-1)

    =Θ( n*log2(n) )

    希望如上回答對您有幫助!

    • Commenter avatar登入以對解答發表意見
還有問題?馬上發問,尋求解答。