O(1)的費氏數列?公式解就一定是O(1)?

我在撰寫此貼文時,原留言者已經刪留言了,反正就是說「費氏數列有公式解,複雜度就是$O(1)$」

於是一堆國手紛紛出籠,然後就……你看就知道了
原文連結:https://www.facebook.com/groups/pythontw/permalink/10158445814613438/

甚至出現 「$\pi$ 跟 $e$ 都存在月球上,這樣就存取最快了,$O(1)$!」

(果然用爛留言去釣高手是最快的辦法,$O(1)$!)


版上的大神在反串什麼?

首先,先來簡單介紹時間複雜度(這只是大眾版的)
要計算最壞的時間複雜度我們會用 big-O

假設$n$是資料個數 或 計算大小
$O(1)$是常數複雜度
意思是說:計算量不會與 $n$ 的大小有任何關係,Ex.$1+2+…+N$的公式解

$O(\log{n})$是對數複雜度
意思是說:計算量會與 $n$ 的大小呈現對數關係,Ex.二分搜尋法

$O(n)$是線性複雜度
意思是說:計算量會與 $n$ 的大小呈現線性(直線)關係

公式解就一定是O(1)?

從1加到N的算式可以寫成這樣
$1+2+…+N=\dfrac{n(n+1)}{2}$

算式就要做一次乘法跟一次除法

不論$N$開多大,開到$10^{100}$,算式都只要做一次乘法跟一次除法就好

可是費氏數列有公式解

$Fibonacci(n)=\dfrac{\sqrt{5}}{5} \cdot \left[\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n} - \left(\dfrac{1 - \sqrt{5}}{2}\right)^{n}\right]$

對,費氏數列有公式解,但是它不是$O(1)$

關鍵就是這個$\left(\dfrac{1 + \sqrt{5}}{2}\right)^{n}$ 跟 $\left(\dfrac{1 - \sqrt{5}}{2}\right)^{n}$

要算第$100$項,這東西就要乘$100$次
要算第$10000$項,這東西就要乘$10000$次
要算第$10^9$項,這東西就要乘$10^9$次

所以這是線性複雜度$O(n)$
(高手就知道這是$O(\log{n})$,這可以矩陣快速冪)

$O(1)$的意義不是在快,而是資料量大小不論多少,他都是固定的計算次數。

如果今天我設計了一個函數:
$n=1$,要計算次數是$10^8$,
$n=10^6$,要計算次數是$10^8$,
$n=10^{100}$,要計算次數是$10^8$,
不論$n$的大小,計算次數都是$10^8$。

時間複雜度:$O(1)$,因為計算次數跟$n$沒有任何關係

總結

要下什麼總結呢?我只知道原Po在原文被歪樓後就被邊緣了QQ

然後原留言者也刪留言、關臉書了。

如果討論是一直在堅持自己的意見,那就不叫討論了

結果變成競程選手們茶餘飯後的話題

整體過程大概就是這樣啦!如果有錯誤,歡迎在底下留言討論!

2019/02/15 更新

新文朝聖:https://www.facebook.com/groups/pythontw/permalink/10158487765003438/