推 KanzakiHAria: 你應該沒搞懂那個討論 02/16 06:33
→ KanzakiHAria: O(1)是說費式數列有一個公式解 02/16 06:33
→ KanzakiHAria: 可是裡面有開根號 所以實務上並不是O(1) 02/16 06:34
→ KanzakiHAria: 開根號速度跟數字長度有關係 02/16 06:34
→ KanzakiHAria: 那個作者非常智障的嗆人time it 實際上就不是O(1) 02/16 06:35
→ KanzakiHAria: 那個人履歷蠻漂亮的 電機出身+待過微軟開發過VS前期 02/16 06:36
→ KanzakiHAria: 看他講話好像連基本的計算機原理和演算法數學都不懂 02/16 06:36
→ KanzakiHAria: 連我以前當助教的學生都可以電爆他了XD 02/16 06:37
推 KanzakiHAria: 講錯了 不是開根號 是次方問題 02/16 06:41
推 KanzakiHAria: 然後O(n)裡的n 一種是編碼長度 一種是input數量 02/16 06:47
→ KanzakiHAria: 因為是編碼長度問題 所以實際上是O(lgn) 02/16 06:49
推 KanzakiHAria: 不過說不定原作者是想表達C++有編譯時期運算技術 02/16 06:52
→ KanzakiHAria: 所以不管n多大C++都會在編譯時期算好 02/16 06:52
→ KanzakiHAria: 所以run-time是O(1)wwwwwwwwww 02/16 06:52
推 alan23273850: 神奇給推! 02/16 08:57
→ KanzakiHAria: 已經跟地球月球時間無關 而是根本上錯誤 02/16 08:57
推 steve8625: 真有趣~~ 02/16 11:55
推 b98901056: Vtuber compiler XD 02/16 12:44
推 firejox: 以編碼長度來看,也不會是O(lg n) 02/16 20:02
→ Sanvean: 我是不是錯過了什麼新聞? 求費氏數列的討論串 pAq 02/17 14:45
→ Ommm5566: ㄟ 這是兩件事 1. O(logN) 是因為乘法有快速乘法logN 02/17 17:14
→ Ommm5566: 2. turing machine來看編碼長度確實是logN 02/17 17:16
→ Ommm5566: 然後巧合的是剛好這兩件事可以掛勾在一起 02/17 17:17
推 Ommm5566: 這個討論串居很無聊,居然這麼多人關注。 02/17 17:20
推 LPH66: 樓上的兩個 logN 是不同 N 吧? 02/17 20:02
→ LPH66: 你的"快速乘法"的 log N 的 N 是編碼長度 02/17 20:02
→ LPH66: turing machine 編碼的 logN 的 N 是數值本身 02/17 20:03
推 Ommm5566: Fabonacci(X) 這個是編碼長度logX 所以放在tap上是logX 02/17 20:19
→ Ommm5566: 然後公式解是一個const連乘X次 02/17 20:20
→ Ommm5566: 因為有快速乘法所以時間是logX 02/17 20:21
→ Ommm5566: 這題只是剛好快速乘法的行為跟二進為編碼直接有相關 02/17 20:21
推 Ommm5566: 1000 是四位數編碼 100是三位數編碼 10是兩位數編碼 02/17 20:24
→ Ommm5566: 放在tap上長度本來就是logN 02/17 20:24
推 KanzakiHAria: 所以正確來說編碼長度N的費氏數列時間複雜度O(N) 02/17 21:32
推 KanzakiHAria: 前面可能我表達不好 這個應該沒爭議了吧 02/17 22:36
推 AstralBrain: O(N)次乘法, 但是乘法的時間不一定是O(1), 看你要怎 02/18 02:33
→ AstralBrain: 麼算 02/18 02:33
→ AstralBrain: 算出沒誤差的精確值至少是O(2^N), 因為答案本身就有 02/18 02:34
→ AstralBrain: O(2^N)bit了 02/18 02:34
推 AstralBrain: 啊..修正一下, 底不確定是不是2, 但總之是指數級成長 02/18 02:53
→ gus2: 怎麼推文都在回討論串?本文重心是編譯器優化遞迴f(i)成i吧 02/18 03:13
推 gus2: 有趣給推 02/18 03:15
→ Caesar08: 請問Higana,這是在哪個社團,那麼有趣 XD 02/18 13:04
推 asd456fgh778: 樓上 Python台灣 02/18 14:42
推 Higana: 是的 但該篇他老早就刪了 剩一些後續討論這樣 02/20 01:44