最近有个热门的讨论话题
就是计算费氏数列的复杂度到底是 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台湾

是的 但该篇他老早就删了 剩一些后续讨论这样