? 發問時間: 社會與文化語言 · 1 0 年前

[電腦複雜度]急急急!!!請問一下這個問題

5.For the following procedure A, analyze and provide the worst case time

complexities. We will use the following assumptions:

Suppose A and B are both procedures. B take θ(n) time to compute,

where n is the size of input. Function A is a recursive one defined

as follows

---

Procedure A(a1,a2,a3,...,an)

1. if(n<=8) then call B(a1,a2,a3,...,an)

2. else { call A(a1,a2,a3,...,a(n/2));

3. call A(a(n/2+1),...,an); }

4. call B(a2,a4,a6,....,am)

/* m is the closest but smaller even number to n */

5. return;

---

請問答案是nlogn嗎?

1 個解答

評分
  • Leslie
    Lv 7
    1 0 年前
    最佳解答

    因為每次分為兩半 ("分"不必特別花的時間, "合併"時才要)

    所以 A 這個 recursion 的深度為 O(log n), 即, 共 O(log n) 層.

    當分成的問題夠小時 (n <= 8 時), 直接解

    (即, 執行第一行的 B, 及第 4 行的 B), 此最深層總共花 O(n+(n/2)). --- (1)

    (註: a2, a4, ..., am 的個數約為 n/2)

    當要合併時 (即, 分成的兩半都解出後, 要回上一層),

    又要執行 B (第 4 行), 要花 O(N), 這個 N 是合併後的資料個數, 在

    某一層的 N 總共為 n.

    因此, 合併共要: (層數)*(每層的合併時間) = O((log n)*(n)). --- (2)

    (1) 加上 (2), 答案是 O(n log n).

    或是, 解 recurrence relation:

    T(n) = 2T(n/2)+O(n) for n>8, with T(n)=O(1) for n<=8. 也可得 T(n)=O(n log n).

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