Q91.
有一遞迴(Recursive)程式如下，下列何者是這個程式的時間複雜度(Time Complexity)？
電腦軟體設計共同科目 · 乙級 · Q91
難易度分析
2 / 5
本題考查對遞迴結構與時間複雜度之間對應關係的理解，需能準確區分線性遞減與問題規模減半在複雜度量級上的差異。
正確答案：③θ(n)
③ θ(n):該遞迴程式每次呼叫自身一次且問題規模遞減 1，總共執行 n 次遞迴呼叫，因此時間複雜度為 θ(n)，屬於典型的線性遞迴結構。
錯誤選項解析
- ① θ(log n):θ(log n) 適用於每次將問題規模減半的遞迴演算法（如二元搜尋），此程式每次僅遞減常數值而非減半，故不適用。
- ②
:此選項（圖片所示）應為 θ(n²) 複雜度，通常出現在雙層遞迴或巢狀迴圈情境（如氣泡排序），此程式僅單層線性遞迴，未達平方級別。 - ④ θ(n log n):θ(n log n) 常見於分治法演算法（如合併排序、快速排序平均情況），需要將問題分割後再合併，此程式無此分割合併結構。
Learning Tip
"本題核心考點為遞迴時間複雜度分析。判斷遞迴程式複雜度時，需觀察每次遞迴呼叫的次數與問題規模縮減方式：若每次遞減 1 且呼叫一次為 θ(n)；若每次減半且呼叫一次為 θ(log n)；若分割為兩子問題且各呼叫一次為 θ(2ⁿ)。實務上常混淆線性遞迴與二元遞迴的差異，需特別注意遞迴樹的分支數量。"
學員答題分佈
①θ(log n)0%
②0%
0%③θ(n)0%
④θ(n log n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
