若n＞=1 時，T(n)=3T(n/3)＋2n，且T

電腦軟體設計共同科目 · 乙級 · Q106

=30，T(n)之複雜度何者正確？(1)T(n)=θ(n)

T(n)=θ(n 2)

T(n)= θ(n log n)

T(n)= θ(log(log n))

3 / 5

本題考查遞迴關係式的漸進複雜度分析，要求對演算法分析的核心定理有精確的掌握，並能正確判斷函數增長速率的對比關係。

③ T(n)= θ(n log n):依據主定理（Master Theorem），a=3、b=3，故 n^(log_b a) = n^1 = n，而 f(n)=2n = Θ(n)，符合第二種情況（f(n) 與 n^(log_b a) 同階），因此 T(n) = Θ(n log n)。

① =30，T(n)之複雜度何者正確？(1)T(n)=θ(n):Θ(n) 的複雜度適用於遞迴樹每層工作量遞減的情況，但本題中 a=3、b=3，使得 n^(log_b a) = n，且 f(n)=2n 與之同階，應落入主定理第二種情況，故線性複雜度不正確。
② T(n)=θ(n 2):Θ(n²) 的複雜度遠高於實際值，此結果通常出現在每層子問題規模縮小但合併成本為二次方的情況，本題的遞迴關係式不支援此結論。
④ T(n)= θ(log(log n)):Θ(log(log n)) 是極低的複雜度，僅見於極少數特殊演算法（如 van Emde Boas 樹），與本題遞迴關係式的增長特性完全不符。

"本題核心考點為主定理（Master Theorem）的三種情況判斷。關鍵在於比較 f(n) 與 n^(log_b a) 的增長速率：當兩者同階時即為 Θ(n log n)。常見陷阱是誤將係數（如本題的 2n）當作判斷依據，實際上應忽略常數係數，僅比較漸進增長階數。"

①=30，T(n)之複雜度何者正確？(1)T(n)=θ(n)0%

②T(n)=θ(n 2)0%

③T(n)= θ(n log n)0%

④T(n)= θ(log(log n))0%

此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！