时间复杂度是 O(2ⁿ)，空间复杂度是 O(n)。你看到的递归调用会形成一棵二叉树，每个节点调用一次 fib。这就是为什么斐波那契适合用作记忆化优化的教学案例——试试加一个 cache 看看会怎样。

没错！时间复杂度降到 O(n)，空间复杂度仍是 O(n)（cache 占用的）。再进一步，可以改成自底向上的循环版本，把空间复杂度也压到 O(1)。要我帮你写一下吗？