最近有个热门的讨论话题 就是计算费氏数列的复杂度到底是 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(n)，也不管 lookup table 到底要不要存在月球上 费氏数列递回的形式都是这条：F(x) = F(x-1) + F(x-2), F(1) = F(2) = 1 不过今天要讨论的是一个更简单的问题 F(x) = F(x-1)+1, F(0) = 0 学过中学以上归纳法的人类都能知道 F(x) = x 而学过 C++ 的人都可以把这个式子转换变成程式码 int Identity(int i) { if (i == 1) return 1; else return Identity(i-1)+1; } 上面的 wiki 说明了这个并不是有效的 tail recursion 形式 理论上应该不会变成 for loop 会产生 O(n) memory, O(n) runtime 的程式 （PS: 如果是 for loop，应该是 O(1), memory O(n) runtime） 为了验证，我用了 gcc 8.2.1 编译看看，结果大出意外 % g++ a.cpp -c -O2 && objdump -d a.o Disassembly of section .text: 0000000000000000 <_Z8Identityi>: 0: 89 f8 mov %edi,%eax 2: c3 ret Linux 下 x64 的第一个整数是 %edi，回传值放在 %eax 等等，所以我以为 O(n) 的问题，真的可以在 O(1) 解出来吗（误） 难道 compiler 做了一些数学计算，推出 F(x) = x 了吗 该不会在这个大 AI 时代，compiler 也要内建高中生等级的 super AI 了吧 该不会我下次升级到 gcc 9 的时候，我的 compiler 就会跑去当 Youtuber 了吧？！ --- Sorry 扯远了，回归正题 我一开始的想法是 1. gcc 知道了 negative i 会撞到 UB，因此可以随便回传任何值 （PS: negative i 不会变成 infinite loop 的 UB，而是 overflow） 2. positive i 的情形 gcc 经过了某些数学推导算出 F(x) = x 但是怎麽看都觉得太神奇，感觉不会有人实做这种东西 总之经过 stackoverflow 一番讨论之後 看起来的结论如下 首先，当代的 gcc 不只可以化简基本的 tail recursion 就连上面那个形式都可以（可以去看 stackoverflow 的一些讨论） 虽然详细上原理我不太明白，但是应该、大约、好像会变成这样子 int Identity(int i) { int ans = 0; for (; i != 0; i--, ans++); return ans; } 接着我猜测这个形式对 compiler 来说应该比较好化简了 因为这种 for loop 非常常见，应该有机会做某种化简得到 F(x) = x 顺带一题，直接写这个程式的话，gcc 是可以化简 O(n) -> O(1) 的 如果 i != 0 改成 i >= 0 的话，gcc 会变成 return i > 0 ? i : 0; 真的很厉害 --- 另外 stackoverflow 里面有人直接挖出 gcc code 来解释 但是其实我不是 compiler 专家 所以我这篇主要还是单纯分享一些我的观察啦 如果这个版有人能做出更浅显易懂，又更完整的解释的话就太好了 谢谢大家～ -- Time waits for no one. ↑ (。Ａ。)ハァ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 118.160.89.176 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1550249453.A.382.html