Anonymous
Anonymous asked in 教育與參考考試 · 1 decade ago

merge sort 的時間複雜度

請問T(n)=2T(n/2)+O(n)是如何而來?

又如何能推倒出T(n)=O(n log n)?

書上推倒過程第一步就看不懂了↓↓↓

2T(n/2)+O(n)=>2(2T(n/4)+O(n/2))+O(n)

我很笨拜託請大大詳解,讓我了解20點奉上

2 Answers

Rating
  • Leslie
    Lv 7
    1 decade ago
    Favorite Answer

    1.

    設 T(n) 是 n 個數的 list 用 merge sort 所須時間.

    Merge sort 的作法是把兩個 lists (各有 n/2 個排好的數) 合併得到答案.

    因此, T(n) 含合併的時間, 以及必須先把兩個 lists 排好要花的時間.

    合併的時間是線性的 O(n) 時間;

    有 n/2 個數的 list 要排好, 使用 merge sort (遞迴) 要 T(n/2) 時間;

    因此, 共花 O(n) + 2T(n/2),

    即 T(n)=2T(n/2)+O(n).

    2.

    用疊帶的方式來解, 如下:

    原式-- T(n)=2T(n/2)+O(n)

    把原式的 n 用 n/2 帶入, 得 

    第二式-- T(n/2)=2T(n/4)+O(n/2).

    把第二式帶入原式中的 T(n/2), 得

    T(n)=2(2T(n/4)+O(n/2))+O(n).

    接下來類似, 上式中的 T(n/4), 可用

    T(n/4)=2T(n/8)+O(n/4) 帶入,

    得 T(n)=2(2(2T(n/8)+O(n/4))+O(n/2))+O(n),

    即 T(n)=(2^3)T(n/8)+[3*O(n)].

    再一直類似的迭帶, 直到 (設 n=2^k)

    T(n)=(2^k)T(n/n)+[k*O(n)]

    因為 T(1)=0, 所以 T(n)=kO(n)=(logn)O(n)=O(nlogn)

    2010-03-01 10:00:22 補充:

    > 這邊看不懂[把第二式帶入原式中的 T(n/2)]!!

    原式是 T(n)=2T(n/2)+O(n),

    這式子的右邊有出現 T(n/2),

    我們若把這個 T(n/2) 換成 2T(n/4)+O(n/2)

    (利用第二式, 因為第二式是成立的),

    則原式就變成 T(n)=2(2T(n/4)+O(n/2))+O(n).

    2010-03-02 11:45:42 補充:

    首先, 令 n=2^k (則 k=logn)

    ... ... ...

    帶入一次得到

    T(n)=2^2)T(n/4)+[2*O(n)]

    再帶一次, 得到

    T(n)=(2^3)T(n/8)+[3*O(n)].

    再一直類似的帶入, 若是帶了 k-1 次,

    就得到

    T(n)=(2^k)T(n/(2^k))+[k*O(n)]

    其中的 T(n/(2^k))=T(n/n)=T(1)=0 (一個數不用運算就排好了, 所以 T(1)=0)

    所以 T(n)=(2^k)*0+[kO(n)]=0+[(logn)O(n)]=O(nlogn)

    Source(s): Algorithm textbooks
    • Login to reply the answers
  • 1 decade ago

    大大請問一下

    2.用疊帶的方式來解, 如下:

    原式-- T(n)=2T(n/2)+O(n)

    把原式的 n 用 n/2 帶入, 得 

    第二式-- T(n/2)=2T(n/4)+O(n/2).

    把第二式帶入原式中的 T(n/2), 得

    T(n)=2(2T(n/4)+O(n/2))+O(n).

    這邊看不懂[把第二式帶入原式中的 T(n/2)]!!

    2010-03-01 22:26:30 補充:

    大大 謝了~那邊看懂了但是下面又看不懂..

    再一直類似的迭帶, 直到 (設 n=2^k)

    T(n)=(2^k)T(n/n)+[k*O(n)]

    因為 T(1)=0, 所以 T(n)=kO(n)=(logn)O(n)=O(nlogn)

    kO(n)=(logn)O(n)是怎麼倒出來的!! 感謝!!

    • Login to reply the answers
Still have questions? Get your answers by asking now.