Q90.
有一遞迴(Recursive)程式如下，下列何者是這個程式的時間複雜度(Time Complexity)？
電腦軟體設計共同科目 · 乙級 · Q90
難易度分析
3 / 5
此題要求分析遞迴程式的執行效率。考生必須能正確判斷遞迴呼叫的次數與深度，並將其轉化為時間複雜度的數學表示式。由於選項中包含多種容易混淆的複雜度量級，需要精確區分指數成長與多項式成長的差異。
正確答案：①
① :此遞迴程式在每次呼叫時會產生兩次遞迴呼叫，形成二元遞迴樹結構，其遞迴樹深度為 n，每層節點數呈指數成長，因此時間複雜度為 θ(2ⁿ)，屬於指數時間複雜度。
:此遞迴程式在每次呼叫時會產生兩次遞迴呼叫，形成二元遞迴樹結構，其遞迴樹深度為 n，每層節點數呈指數成長，因此時間複雜度為 θ(2ⁿ)，屬於指數時間複雜度。錯誤選項解析
- ②
:θ(n) 為線性時間複雜度，僅適用於每次遞迴僅產生單一呼叫且遞迴深度為 n 的情況（如階乘計算），但本題程式每次呼叫會產生多個遞迴分支，故不適用。 - ③
:θ(n²) 為多項式時間複雜度，通常出現在雙層巢狀迴圈或特定遞迴結構，但本題的二元遞迴樹節點總數為 2ⁿ 量級，遠大於 n²，因此此選項錯誤。 - ④ θ(n log n):θ(n log n) 常見於分治法演算法（如合併排序、快速排序平均情況），其特徵是將問題對半分割後合併，但本題遞迴結構並非分治模式，而是指數型遞迴，故不正確。
Learning Tip
"在資料結構的遞迴時間複雜度分析中，關鍵在於判斷每次遞迴呼叫產生的子問題數量：若每次產生單一遞迴呼叫為 O(n)；若每次產生兩個遞迴呼叫且無重疊子問題最佳化，則為 O(2ⁿ) 指數型成長。常考陷阱包括混淆 O(2ⁿ) 與 O(n²)，以及誤將二元遞迴認認為分治法的 O(n log n)。實務上應優先使用動態規劃或記憶化技術將指數複雜度降為多項式時間。"
學員答題分佈
①0%
0%②0%
0%③0%
0%④θ(n log n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！