算法面试，写一个斐波那契数高效算法

面试官：同学，你先自我介绍一下吧...
小菜鸟：*A#$b&。。。把自己吹了一遍
...
...
面试官各种问，小菜鸟各种答。

随后面试官拿来一张纸，一支笔，给我写一个斐波那契数算法，输入n，返回第n位的斐波那契数。
小菜鸟心里一笑，花了1分钟，哗哗写了一个函数。

面试官皱了一下眉，你这个函数的时间复杂度多少？
小菜鸟一愣，摸了摸头，不确定的说 O(2^n)

面试官：那还有更快的方式吗？你想想，如果采用递归，算n位的时候，需要计算第n-1和n-2位，计算n-1时需要计算n-2和n-3，有没有发现很多都是重复计算？

小菜鸟拿起笔琢磨了一段时间，写了又划，划了又写，花了点时间，给面试官看了下面的代码。

面试官看了下，点了点头说：现在这个的时间复杂度多少？
小菜鸟这下坚定的说 O(n)

不过面试官好像还不准备放过小菜鸟，时间复杂度还能不能更低？
小菜鸟这下不淡定了，想了好久了，几张纸都涂涂画画了，还是没能写出另一个更优的算法，最终只能摇摇头作罢。

面试结束后，小菜鸟虚心跟面试官请教，斐波那契数的更优解法是什么，可否指点一下。

面试官：可以通过矩阵求解，斐波那契的递推公式可以表示成如下矩阵形式，所以其

所以根据矩阵的分治算法，可以在O(logn)时间内算出结果。

小菜鸟听完一头雾水，只能回去再好好琢磨了。

其实，很多大公司比如BAT、Google、Facebook，面试的时候都喜欢考算法、让人现场写代码。有些人虽然技术不错，但每次去面试都会“跪”在算法上，很是可惜。

为什么这些大公司都喜欢考算法呢？

校招的时候，面试的学生通常没有实际项目经验，只能考察基础知识是否牢固。社招就更不用说了，越是厉害的公司，越是注重考察数据结构与算法这类基础知识。相比短期能力，他们看中你的长期潜力。