我是这么实现斐波那契数列的

[Jakesoft]

实习时面试面到这个问题，当时还不知道斐波那契数列，讲给同学听时，他说，这不就是斐波那契数列吗？！ (尴尬脸）

然后这是我面试的回答:

$total = [0, 1];

for ($i = 2; $i < 100; $i++)
{
	$total[] = $total[$i - 1] + $total[$i - 2];
}

今天看到别人（书本）的实现，需要定义几个变量来交换当前值、上一个值，感觉好麻烦。

还有我的代码应该没啥问题吧

[raysonx]

话说如果只是要求求出某一个 Fibonacci 数而不是整个数列的话，可以直接用公式在 O(1)的时间内求得。

[xiaopc]

@Kilerd 线性递推先构造出矩阵，然后用矩阵乘法结合律降次

[SplendentDraco]

我记得高一时上课时无聊吧这玩意儿通项公式求出来了。。😂

[choury]

@raysonx 公式里面全是无理数，计算机直接算不好吧

[Kilerd]

@loggerhead 重复平方，我懂。

@Contextualist @xiaopc GET 到了。 矩阵方法确实神奇。 至于代数方法，感觉是像是把矩阵方法拆开些而已。

完蛋了，现在看博客都专心不了了。

[chuanqirenwu]

这个面试比较蛋疼，他是要考察你什么呢？斐波拉契数列的定义？还是高效的代码实现？

[Cbdy]

@raysonx 我想了一下没想出来怎么在 O(1)时间内求出来。通项是无理数，比如 n 很大，算出来的精度就很可疑了。有什么好方法吗？ O(1)

[blackjar]

@q397064399 尾递归打开优化 没区别

[Jakesoft]

@GPIO 可能是忘记了吧，不过大学确实很少上课。。。

[h4x3rotab]

@Cbdy 快速矩阵幂， O(logn)

[Jakesoft]

@chuanqirenwu 应该是如何实现“后面一个数等于前两个数之和”吧，至于如何高效实现我还需要花点功夫。

[manongvpn]

会 Google ，你就离大牛近了一步。

[bdbai]

@loggerhead 弱弱问一下，你的博客文章中矩阵为什么乘在向量的右边？

[CFM880]

看下 sicp 里面就有，树形递归和线性迭代，书上讲两种过程的优缺点说的很清楚

[j5shi]

@q397064399 这么浅显的问题要是面试官顺着你的思路真的问了那只能恭喜你局面被你控制了😄

[loggerhead]

@bdbai 这不是矩阵乘法吗？ 1x2 乘以 2x2 的矩阵 = 1x2 的矩阵。你可以看看这个： http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html

[owt5008137]

用矩阵，斐波那契的复杂度是 O （ log （ n ））

[ZRS]

用通项公式...

[q397064399]

@j5shi 我会说很多程序员 并不知道 程序堆栈这回事么？

[longhao]

@q397064399 尝试尾递归呢