hce_nsysu
112年
計算機概論與程式設計
第 13 題
The time complexity of a certain algorithm is calculated by $T(n)=cn+T((1-y)n)$, where $n$ represents the number of input elements, $c$ and $y$ are positive constants, $0 < y < 1$. What is the time complexity?
- A $\Theta(n)$
- B $\Theta(n \log n)$
- C $\Theta(n \log^y n)$
- D $\Theta(n \log^{1-y} n)$
- E $\Theta(n^2)$
思路引導 VIP
試著將這個遞迴式展開成一個級數：第一項是 $cn$，第二項是將 $n$ 替換為 $(1-y)n$ 後產生的工作量。請觀察每一層產生的工作量與前一層相比，是增加了還是減少了？如果每一層都按相同的比例縮減，那麼所有層級的工作量總和，會被第一層的大小所主導，還是會隨著層數增加而無限發散呢？
🤖
AI 詳解
AI 專屬家教
太棒了！你能準確判斷出這類遞迴關係式的複雜度，代表你對演算法的時間分析有著很紮實的直覺。這道題目的核心在於理解**遞迴樹（Recursion Tree）**的加總過程。當我們將 $T(n) = cn + T((1-y)n)$ 展開時，會發現它形成了一個等比級數：總工作量等於 $cn + c(1-y)n + c(1-y)^2n + \dots$。由於 $0 < y < 1$，代表公比 $(1-y)$ 必定小於 1，這是一個收斂的幾何級數。
遞迴關係與幾何級數的收斂
根據等比級數公式，這個數列的和會趨近於 $cn \cdot \frac{1}{1-(1-y)} = \frac{c}{y}n$。因為 $c$ 與 $y$ 都是正常數，整體的計算量與 $n$ 成線性比例，因此複雜度為 $\Theta(n)$。這題的鑑別度在於它使用了抽象的常數 $y$ 而非具體數字（如常見的 $T(n/2)$），考驗學生是否能跳脫公式死背，從遞迴縮減比例的本質來思考。這屬於中等難度的題目，能迅速答對代表你對大 $O$ 符號的漸進分析掌握得非常出色！