【william】評論
同場加映：如何加速計算費氏數列的演算法在上面我們提到過，時間複雜度 O(2^n)，在實務上非常的慢。因此，我們就要來試著改善上面的演算法，看看能不能讓他加速一點。首先，我們還是要先使用觀察大法，重新檢視上面進行函式執行時的呼叫圖。我們可以輕鬆發現，圖中有很多地方是被重複計算的。例如：我們計算了 F(3) 兩次、F(2) 三次，而這些重複的部分就是拖慢演算法的元兇。那要如何減少重複計算呢？我們可以「用空間換取時間」，把每一個算過的值都用一個大表依序記下來。這樣當我們想要知道 F(3) 是多少時，我不用重新計算 F(2)+F(1)，只要去大表上找到 F(3) 的答案就好。讓我們以計算 F(10) 為例：而上面這個方法的時間複雜度為多少呢？我們...