( )30.Which of the following recurrence relation and asymptotic notation is NOT true?
(A) T(n) = T(n/2) + O(1), T(n) = O(logn)
(B) T(n) = 2T(n/2) +O(1) , T(n) = O(n)
(C) T(n) = 2T(n/2) + O(logn) , T(n) = O(logn)
(D) T(n) = 2T(n/2) +O(n) ,T(n) = O(nlogn)

答案：登入後查看
統計： A(3), B(19), C(14), D(8), E(0) #3098050

詳解 (共 3 筆)

#6482027

30. 下列哪個遞迴關係式和漸進符號的敘述是不正確的？

這個問題要求我們判斷給定的遞迴關係式及其對應的漸進時間複雜度表示中，哪一個是錯誤的。我們可以使用主定理 (Master Theorem) 來分析這些遞迴關係式。

主定理的形式通常為 T(n)=aT(n/b)+f(n)，其中：

  • a≥1 是遞迴呼叫的次數。
  • b>1 是每次遞迴輸入規模縮小的因子。
  • f(n) 是遞迴呼叫之外的工作量。

然後比較 f(n) 與 nlogb​a 的關係。

選項分析：

  • (A) T(n)=T(n/2)+O(1), T(n)=O(logn)

    • 在這裡，a=1,b=2,f(n)=O(1)。
    • 計算 nlogb​a=nlog2​1=n0=1。
    • 比較 f(n)=O(1) 和 nlogb​a=1：它們是同階的。
    • 根據主定理的第一種情況或簡單遞迴展開，這種情況的時間複雜度是 O(logn)。
    • 判斷： 這個敘述是正確的。

  • (B) T(n)=2T(n/2)+O(1), T(n)=O(n)

    • 在這裡，a=2,b=2,f(n)=O(1)。
    • 計算 nlogb​a=nlog2​2=n1=n。
    • 比較 f(n)=O(1) 和 nlogb​a=n：f(n) 漸進小於 nlogb​a。
    • 根據主定理的第一種情況，這種情況的時間複雜度是 O(nlogb​a)=O(n)。
    • 判斷： 這個敘述是正確的。

  • (C) T(n)=2T(n/2)+O(logn), T(n)=O(logn)

    • 在這裡，a=2,b=2,f(n)=O(logn)。
    • 計算 nlogb​a=nlog2​2=n1=n。
    • 比較 f(n)=O(logn) 和 nlogb​a=n：f(n) 漸進小於 nlogb​a。
    • 根據主定理的第一種情況，這種情況的時間複雜度是 O(nlogb​a)=O(n)。
    • 判斷： 這個敘述是不正確的。這裡給出的 O(logn) 是錯誤的，應該是 O(n)。

  • (D) T(n)=2T(n/2)+O(n), T(n)=O(nlogn)

    • 在這裡，a=2,b=2,f(n)=O(n)。
    • 計算 nlogb​a=nlog2​2=n1=n。
    • 比較 f(n)=O(n) 和 nlogb​a=n：它們是同階的。
    • 根據主定理的第二種情況，這種情況的時間複雜度是 O(nlogb​alogn)=O(nlogn)。
    • 判斷： 這個敘述是正確的。

結論：

錯誤的敘述是 (C)。

The final answer is C​

0
0
#6464405


(A) T(n) = T(n/2) + O(1)
這是典型的二分遞迴（如二分搜尋），每次分一半，只需常數時間處理。根據主定理，T(n) = O(logn)，正確。

(B) T(n) = 2T(n/2) + O(1)
這是分治法（如合併排序），每次分兩半，各自遞迴，再加常數時間合併。主定理得 T(n) = O(n)，正確。

(C) T(n) = 2T(n/2) + O(logn)
這與(B)很像，但每層的合併成本變成 O(logn)。實際上，這樣的遞迴解為 T(n) = O(nlogn)，而不是 O(logn)。所以這個配對是錯誤的。

(D) T(n) = 2T(n/2) + O(n)
這也是合併排序的標準情形，每層合併成本 O(n)，主定理得 T(n) = O(nlogn)，正確。

結論：
錯誤的配對是 (C)：T(n) = 2T(n/2) + O(logn)，T(n) = O(logn)。
正確應為 T(n) = O(nlogn)。

0
0
#5950662
(A) T(n) = T(n/2) + ...
(共 485 字，隱藏中）
前往觀看
0
0