Q92.
有一遞迴(Recursive)程式如下，以下何者是這個程式的時間複雜度(Time Complexity)？
電腦軟體設計共同科目 · 乙級 · Q92
難易度分析
3 / 5
此題要求分析遞迴程式的執行效率，需將程式邏輯轉化為遞迴關係式並應用主定理進行推導，且需精確區分分治法與單純對數時間複雜度的差異，具備一定的分析難度。
正確答案：④θ(n log n)
④ θ(n log n):θ(n log n) 是正確的時間複雜度，此遞迴程式屬於分治法(Divide and Conquer)架構，每層遞迴將問題分割後再合併，符合主定理(Master Theorem)中 T(n) = 2T(n/2) + O(n) 的解。
錯誤選項解析
- ① θ(log n):θ(log n) 通常對應二分搜尋法(Binary Search)等每次將問題規模減半的演算法，此遞迴程式並非單純的對數時間複雜度。
- ②
:此選項對應的圖片內容所示之時間複雜度不正確，該複雜度不符合此遞迴程式的實際執行次數分析。 - ③
:此選項對應的圖片內容所示之時間複雜度不正確，該複雜度高估或低估了此遞迴程式的實際運算步驟。
Learning Tip
"遞迴時間複雜度分析是資料結構常考題型，關鍵在於辨識遞迴關係式並套用主定理。常見陷阱是混淆 θ(log n)（單純二分）與 θ(n log n)（分治合併），需注意每層遞迴是否有額外的 O(n) 合併操作。"
學員答題分佈
①θ(log n)0%
②0%
0%③0%
0%④θ(n log n)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
