關於下述 C 語言程式片段，下列何者為真？ int f(int n) { if ( n == 0) return(0); if ( n <= 2) return(1); return (f(n-1)+f(n-2)+f(n-3)); } k
Af(n) < 3 f(n-3k)
B計算 f(n)至少要花 2O(n)的時間 3正確答案
Cf(n)可在 O(n )的時間內算出答案
Df(n)代表第 n/3 個費氏數（Fibonacci number）
答案與詳解
逐選項解析
Af(n) < 3 f(n-3k)✕ 錯誤
此數列的增長率約為 1.839 的 n 次方，選項中的數學不等式關係不成立。
B計算 f(n)至少要花 2O(n)的時間 3✓ 正確
原程式碼為樹狀遞迴且未使用記憶化，每次展開三個子問題，時間複雜度呈指數成長，即 2 的 O(n) 次方（指數時間）。
Cf(n)可在 O(n )的時間內算出答案✕ 錯誤
Df(n)代表第 n/3 個費氏數（Fibonacci number）✕ 錯誤
立即註冊,看完整詳解
這題的完整詳解,註冊就能看 · 每天 2 題免費
- 完整逐選項解析
- 秒殺解題技巧與破題關鍵
- 關鍵知識表整理
- 陷阱與易錯提醒
- 同考點歷屆題庫連續刷題與錯題本
立即註冊觀看完整詳解 已有帳號?登入
