最近有個熱門的討論話題
就是計算費氏數列的複雜度到底是 O(1) 還是 O(n)
剛好我前幾天在看 wiki 嘗試 compiler 的一些東西的時候
https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8
也遇到一些有趣的 O(1) 還是 O(n) 的問題
覺得很有趣所以就分享上來
我也有把問題丟在 stackoverflow 上面問
沒想到上面的反應也蠻熱烈的
https://stackoverflow.com/questions/54686395
讓我不小心賺到了一些 reputation，大概比我回答十個問題還多

你應該沒搞懂那個討論O(1)是說費式數列有一個公式解可是裡面有開根號 所以實務上並不是O(1)開根號速度跟數字長度有關係那個作者非常智障的嗆人time it 實際上就不是O(1)那個人履歷蠻漂亮的 電機出身+待過微軟開發過VS前期看他講話好像連基本的計算機原理和演算法數學都不懂連我以前當助教的學生都可以電爆他了XD講錯了 不是開根號 是次方問題然後O(n)裡的n 一種是編碼長度 一種是input數量因為是編碼長度問題 所以實際上是O(lgn)不過說不定原作者是想表達C++有編譯時期運算技術所以不管n多大C++都會在編譯時期算好所以run-time是O(1)wwwwwwwwwwhttps://i.imgur.com/N6tFX0a.png

神奇給推！

已經跟地球月球時間無關 而是根本上錯誤

真有趣~~

Vtuber compiler XD

以編碼長度來看，也不會是O(lg n)

我是不是錯過了什麼新聞？ 求費氏數列的討論串 pAq

ㄟ 這是兩件事 1. O(logN) 是因為乘法有快速乘法logN2. turing machine來看編碼長度確實是logN然後巧合的是剛好這兩件事可以掛勾在一起這個討論串居很無聊，居然這麼多人關注。

樓上的兩個 logN 是不同 N 吧?你的"快速乘法"的 log N 的 N 是編碼長度turing machine 編碼的 logN 的 N 是數值本身

Fabonacci(X) 這個是編碼長度logX 所以放在tap上是logX然後公式解是一個const連乘X次因為有快速乘法所以時間是logX這題只是剛好快速乘法的行為跟二進為編碼直接有相關1000 是四位數編碼 100是三位數編碼 10是兩位數編碼放在tap上長度本來就是logN

所以正確來說編碼長度N的費氏數列時間複雜度O(N)前面可能我表達不好 這個應該沒爭議了吧

O(N)次乘法, 但是乘法的時間不一定是O(1), 看你要怎麼算算出沒誤差的精確值至少是O(2^N), 因為答案本身就有O(2^N)bit了啊..修正一下, 底不確定是不是2, 但總之是指數級成長

怎麼推文都在回討論串？本文重心是編譯器優化遞迴f(i)成i吧有趣給推

請問Higana，這是在哪個社團，那麼有趣 XD

樓上 Python台灣

是的 但該篇他老早就刪了 剩一些後續討論這樣