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

栏目: 编程工具 · 发布时间: 6年前

内容简介:面试官:同学,你先自我介绍一下吧...小菜鸟:*...

面试官:同学,你先自我介绍一下吧...

小菜鸟:* 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,面试的时候都喜欢考算法、让人现场写代码。有些人虽然技术不错,但每次去面试都会“跪”在算法上,很是可惜。

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

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

面试过程中表现出来的算法能力,可以为本次面试加分不少,对于想在算法方面提高的同学,我这里推荐极客时间刚上不久的一个专栏,涵盖了100多个算法真实项目场景案例,作者还亲自画了一些清晰易懂的详解图,帮你理解核心概念和实现过程,展示每个知识点的框架逻辑,让晦涩难懂的算法变得轻松有趣。

这个算法专栏真的受欢迎,刚上线1天,已经突破17000的订阅

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

想订阅的同学,可以扫下面的二维码,加入学习,提高算法思维能力。

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Hive编程指南

Hive编程指南

卡普廖洛 (Edward Capriolo)、万普勒 (Dean Wampler)、卢森格林 (Jason Rutherglen) / 曹坤 / 人民邮电出版社 / 2013-12-1 / 69

市场中第一本Hive图书。 Hive在Hadoop系统中的应用趋势比较可观。一起来看看 《Hive编程指南》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具