費氏數列（Fibonacci number）之定義如下：假設 $n_{0} = 0$ ， $n_{1} = 1$ ，則 $n_{2} = n_{1} + n_{0} = 1 + 0 = 1$ ， $n_{3} = n_{2} + n_{1} = 1 + 1 = 2$ ，…， $n_{i} = n_{i - 1} + n_{i - 2}$ 。若以遞迴法撰寫程式計算費氏數列，給定一個 $n$ 值，求解費氏數列第 $n$ 項的值，請問時間複雜度為何？

O (n)

O (n^{2})

O (n lo g n)

O (2^{n})

正確答案

答案與詳解

正確答案

純遞迴費氏數列每次呼叫產生兩個子呼叫,遞迴樹近似滿二元樹,時間複雜度為

O (2^{n})

。

正確。遞迴樹每層分兩枝,深度約 $n$ ,節點數約 $2^{n}$ ,故為 $O (2^{n})$ 。

載入中…

Examly 收錄 38 萬+ 道歷屆題目，每題都有像這樣的精選詳解。免費下載，立即開練。