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

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

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

~~（果然用爛留言去釣高手是最快的辦法，$O(1)$！）~~

版上的大神在反串什麼？

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

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

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

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

從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

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

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