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，我們可以假設我們移動的都是多出來的 edges，不必去動原本的 n-1 個 edges。

假設原本的 graph 被切分成分離的 m 塊 connected components，則我們需要移動 m-1 個 edges 去連接，因此問題變成了找出目前有幾塊 connected components。