Algorithm

在上篇我們討論了費氏數列的各種基本解法。

原本我也以為 O(n) 的迭代解就已經是標準解法了，直到被大神朋友指正：

問費氏數列應該是想聽 $O(\lg n)$ 解法吧？

查了一下還真的有，這篇文章寫得蠻完整的，這篇會參考該篇文章來撰寫，但會用我自己的話以及 Python 寫出來。

面試被問到的題目，雖然是很基本的題目，但相關延伸也有不少，寫篇文章記錄一下。

遞迴：最基本又直觀的解法

使用情境 在 Leetcode 寫到一題： 1319. Number of Operations to Make Network Connected 現在有 n 台電腦以及一些 cables 將電腦點對點連接，問需要移動至少幾條 cable 才能讓在所有電腦連成單一網路。 以 graph 的角度來看，電腦就是 nodes，cables 就是 edges。 要將整張 graph 連接起來，至少需要 n-1 個 edges。若一個 graph 裡面有超過 n-1 個 edges，剩下的就是多出來的 edges，可以供我們拿來移動的 edges。 所以第一件事就是要檢查 edges 數量 >= n-1。 當檢查完畢之後，我們有至少 n-1 條 edges，一定可以用這些 edges 將所有 nodes 連接起來。 因為題目只問需要移動幾條 edges，我們可以假設我們