給定遞迴時間複雜度(time complexity)方程式 $\mathrm{T(n)} = \mathrm{T(n / 3)} + \mathrm{n}$ for $n > 1$ 其初值 $\mathrm{T(1)} = 5$ ，下列敘述何項錯誤？

初考-統計資料處理大意108 年第 16 題單選題

給定遞迴時間複雜度（time complexity）方程式 $T (n) = T (n /3) + n$ for $n > 1$ 其初值 $T (1) = 5$ ，下列敘述何項錯誤？

T (3) = 8

T (9) = 17

T (27) = 44

T (n) \in O (n l g n)

正確答案

答案與詳解

正確答案

本題考查遞迴方程式的數值計算與時間複雜度分析。數值部分直接代入即可驗證，時間複雜度則透過大師定理（Master Theorem）可求得為 O(n)，故選項 D 錯誤。

載入中…