Q108.
若n＞=1 時，T(n)＝8T(n/2)＋6n，且T(1)＝6，T(n)之複雜度何者正確？
電腦軟體設計共同科目 · 乙級 · Q108
難易度分析
3 / 5
本題要求運用特定數學定理分析遞迴時間複雜度，需精確計算遞迴參數並判斷其增長級別。由於涉及多個選項間的漸近複雜度比較，且需正確區分不同情況下的主導項，具有一定的計算與理論分析要求。
正確答案：④θ(n 3)
④ θ(n 3):根據 主定理（Master Theorem），a=8、b=2，計算 n^(log_b a) = n^(log₂ 8) = n³，而 f(n)=6n = O(n³⁻ᵉ)，符合 Case 1，故 T(n) = θ(n³)。
錯誤選項解析
- ① θ(n(log n)2):θ(n(log n)²) 常見於特定分治演算法如 Strassen 矩陣乘法 的變體，但本題遞迴樹的分支數 a=8 遠大於子問題縮減因子 b=2，其增長速率遠超 n(log n)²，故此選項錯誤。
- ② θ(n2):θ(n²) 通常對應 a=4、b=2 的遞迴關係（如某些二維分治問題），本題中 log₂8 = 3，主項為 n³ 而非 n²，混淆了不同遞迴參數的結果。
- ③ θ(nlog n):θ(n log n) 是 合併排序 或 快速排序平均情況 的複雜度，對應 a=b=2 的情形，本題 a=8 導致遞迴樹節點數呈指數增長，遠大於 n log n。
Learning Tip
"本題核心考點為 主定理（Master Theorem） 的三種情況判斷。關鍵在於正確計算 log_b a 並與 f(n) 比較增長速率：當 f(n) 多項式小於 n^(log_b a) 時屬 Case 1，解為 θ(n^(log_b a))。常見陷阱是誤算 log₂8 或混淆 Case 1 與 Case 2 的適用條件，實務上應熟記 a 代表遞迴分支數、b 代表問題縮減倍率的意義。"
學員答題分佈
①θ(n(log n)2)0%
②θ(n2)0%
③θ(nlog n)0%
④θ(n 3)0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
