斐波那契访谈

斐波那契数列的计算是一项经典的算法任务，因为通常在面试中，当他们想要验证候选人在某种程度上至少能够在算法中进行时，才会在访谈中给出该计算。 假设您是同一候选人。 您得到了任务：在JavaScript中，编写一个函数fib(n) ，该函数返回第n个斐波那契数。 我们认为零斐波那契数为零。 不需要验证参数。 您有什么选择？

1.变得简单，人们会为您服务。

最简单的解决方案是平庸周期。

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

开个玩笑 当然，您不需要这样写-除非，当然，您不会因专职混淆器的职位而接受采访。

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

您的优惠券用完了吗？ 塞浦路斯

好吧，为了获得更高的可读性，让我们这样写：

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

这是一个经典，简单而优雅的选择。 但是也许您想证明您对其他一些概念的了解？ 例如...

2.要了解递归，您必须了解递归

例如，是的，您可以证明可以进行递归。 例如，像这样：

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

记住此选项。 这不值得做。 不应该这样。 这是不可能的。 没关系 这比踢幼犬还差，相当于一场大屠杀。

您可能会问为什么。 在这种情况下，只需运行此代码并尝试计算例如五十斐波那契数。 我认为您会感到有些延迟。 开个玩笑 我相信，如果您不在超级计算机上运行此代码，那么您根本就不会等待结果。 尽管前面的示例中的简单，非递归代码将比您有时间说出“五十”或任何音节更快地对斐波那契数列的第五十个成员进行计数。

用O符号的粗略语言表示，这种解决方案的时间复杂度为O（e ⁿ ）。 即，该函数的执行时间随着n的增加而呈指数增长。 即，当n增加时，执行时间增加。 粗略地说，如果您要等待一个小时fib(45) ，那么fib(46)您将要等待两个小时， fib(47) -4小时，依此类推。 我仔细地咀嚼一下，以至于每个读者，甚至是最先尝试写脚本的排字工人都可以意识到这种情况的恐怖。

这是正确的，但过于粗鲁。 您可以对函数调用的数量〜（1 + sqrt（5））fib（n）进行更准确的估算，并提供精美的注释：“要使用朴素的递归方法来计算斐波那契数，您需要的函数调用比斐波那契数本身多3.2倍。” 金牛座

我们得到了另一种计算方法。 您只需要运行朴素的递归方法，计算函数调用的数量并除以3.2！ Cerberuser

如果要求您在面试中递归解决此问题，则很可能是陷阱。 例如，在线性时间内工作的“正确”递归可能看起来像这样：

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

总结：尽管斐波那契数是经典的递归示例，但实际上这并不是应用递归最方便的情况。 但是您可以尝试炫耀一些更多的知识。

3.纪念功能

有一种神奇的方法可以将最后一段中极其无效的解决方案变成可能非常快速的解决方案（尽管并非没有问题）。 他的名字是回忆。 如果您说俄语，我们会记住以前的通话结果，而无需重新计算。

基本上，我们甚至无法更改该解决方案中的任何内容-只需添加一个memoize包装器函数即可。 在这里，为清楚起见，我将其简化版本用于带有单个参数的函数。

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

瞧！ 现在， fib函数可以通过关闭访问cache对象。 如果使用以前未遇到的参数调用它，则计算出的值将存储在cache 。 使用具有相同参数的新函数调用，不必重新计算该值，只需从高速缓存中获取该值即可。 “错误的”旧fib函数的主要问题是其中的相同值被重新计算了几次。 例如，要计算fib(45)必须计算一次f(44) ，两次f(43) ，三次f(42) ，五次f(41) ，依此类推。


因此，现在以前的值将被计算一次，并且在重新请求它们时-将从缓存中获取。 您能想象我们现在可以更快地计算出第四十五斐波那契数吗？ 认真的，你觉得什么时间？

实际上-慢一点。 我故意犯了一个经典错误，在记述递归函数时经常犯此错误。 当将fib(45)称为“引擎盖下”时， oldFib(45)调用oldFib(45) ，它会根据需要来调用oldFib(44)和oldFib(43) 。 在下文中，已经有对常规非记忆功能的调用。 当然，再次调用fib(45)时，我们会立即从缓存中获取结果-但是，第一次调用根本没有加快速度。 要解决此问题，您仍然必须在扳手底部下方找到oldFib ：

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

太好了！ 现在，对fib(45)的首次调用fib(45)与具有循环的版本相当的速度工作。 而且，进一步的挑战通常会在固定的时间内发挥作用。 再次受骗。 通过键获取对象属性的值是一项快速操作，但是O（1）仍然只是平均值，在最坏的情况下，它可能降级为O（n）。 为了使其非常好，在我们的例子中，我们可以将cache的类型从对象更改为数组。

当然，不要忘了记忆需要记忆。 在减少时间复杂度的同时，内存复杂度也从O（1）增长到O（n）。

我们还能如何炫耀？ 例如，展示您对数学的深入了解

4. Binet先生

关于如何将递归关系转换为明确的公式，这是一门特殊的奇妙科学。 在这里我们不再赘述。 我们只会说，对于斐波那契数，使用相当简单的参数，我们可以得出以下公式，即Binet公式：

$$

$$F_n = \ frac {\左（\ frac {1 + \ sqrt5} {2} \右）^ n-\左（\ frac {1-\ sqrt5} {2} \ right）^ n} {\ sqrt5}$$

但是，这是一种数学语言，我们用JavaScript编写：

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

让我们继续前几个数字。 太好了，似乎一切正常。 这里是13，这里是21，这里是34，这里是... 54.9999999999999999？

是的，当然，这样的结果是合乎逻辑的。 Binet的公式在数学上是准确的，但是计算机以有限的精确度进行运算，并且在使用它们进行运算时可能会累积错误。 但是，我们可以修复它。 知道分子中的减法将始终很小，因此可以将公式简化为以下状态：

$$

$$F_n = \左\ lfloor \ frac {\左（\ frac {1 + \ sqrt5} {2} \ right）^ n} {\ sqrt5} \ right \ rceil$$

这里奇怪的未完成的方括号表示最接近的整数，即四舍五入。 重写我们的代码：

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

是的，那要好得多。 我们可以看到55和89，甚至我最喜欢的斐波那契数是144（我喜欢它，因为它等于十二个平方）。 直到数字76一切都会好起来。该数字应等于3416454622906707，我们的函数将计算出3416454622906706。由于分数精度有限的问题没有消失，我们只是将其推得更深，希望它不会出现。 如本例所示，他们希望徒劳。

实际上，我们可以做一些其他事情来保存此方法。 但是下面有更多关于它的内容。 在此期间-开个玩笑。 让我们谈谈苛刻，顽固和残酷的方法。

5.跟随白兔子。

他们说，如果您有问题，并且想到了可以使用正则表达式解决的想法，那么您现在就有两个问题。 相反，矩阵是正则表达式。 如果用矩阵语言重新表述的话，许多问题可以自己解决。

至于斐波那契数，对于矩阵式的斐波那契数，您可以写下这个明显的标识：

$$

$$\开始{pmatrix} 0＆1 \\ 1＆1 \结束{pmatrix} \开始{pmatrix} F_ {n-1} \\ F_n \ end {pmatrix} = \开始{pmatrix} F_n \\ F_ {n +1} \结束{pmatrix}$$

也就是说，如果我们采用一对连续的斐波那契数并将它们乘以这样一个简单的矩阵，我们得到以下对。 逻辑结论由此得出：如果我们取一对零和第一个斐波那契数，即零和一个，然后将它们乘以该矩阵乘以n次方，则得到一对nth和en加第一个斐波那契数。 也就是说，以人为本：

$$

$$\开始{pmatrix} 0＆1 \\ 1＆1 \结束{pmatrix} ^ n \开始{pmatrix} 0 \\ 1 \ end {pmatrix} = \开始{pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

您可以通过放弃向量来进一步简化此过程。 实际上，所有必要的值都包含在矩阵本身中：

$$

$$\开始{pmatrix} 0＆1 \\ 1＆1 \结束{pmatrix} ^ n = \开始{pmatrix} F_ {n-1}＆F_ {n} \\ F_ {n}＆F_ {n + 1 } \结尾{pmatrix}$$

很好，不是吗？ 如果他不是爱乐乐团，那还有什么要和他和谐相处的呢？ 我的意思是-为什么这样的困难突如其来。 答案很简单-快速求幂。

例如，计算2 ¹⁰需要多少个基本乘法？ 一个正常的人会说九点。 两次两次-两次。 两次四点至八点。 两次八点十六分。 依此类推。 狡猾的人会说四。

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

程序员会说。 他记住了这个数字，不需要增加任何东西。 但是，我们在上面讨论了记忆的问题。

因此，快速求幂也适用于矩阵，从而使我们能够将函数的渐近时间复杂度从O（n）降低到O（log n）。 这非常酷-当然，除非这种复杂性对我们如此重要。 让我们编写代码：

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

因此，我们在狂野西部获得了最快的算法。 而且，与以前的大多数方法不同，它可以在采访中以非讽刺的方式加以证明。 在某些具有数学能力的地方，您会期望得到它。

聚苯乙烯

我答应过有关如何保存基于Binet公式的方法的评论。 答案就在我的这篇文章中。 在那儿，出于国民经济的需要，我写了一个特殊的类，五个有理数的根，在不损失准确性的情况下，可以存储整数的算术运算结果和五个根。 您可以使用此类，并用四舍五入方法进行补充，并使用Binet公式搜索斐波那契数。 然后通过快速求幂注入一氧化二氮。

最有趣的是：如果您仔细查看过程中将获得哪些数字，将执行哪些操作，那么很明显，该方法是相同的矩阵乘法，只是在不同的外观下。 唯一的区别是我们是将数字存储在二维数组中还是在特殊类的对象的字段中存储。

仅此而已。 如果您认为我错过了一些其他有趣的方式来查找没人需要的数字，请务必在评论中写下它。

还有一种方法，例如快速倍增 。 它的工作方式类似于O（log）中的矩阵乘法，但渐近线中（以及实际上）的常数较小。 简要地讲，然后在此处使用两个公式，据此可以快速递归地将两个较低的索引回滚：

F _2n = F _n *（2 * F _{n +1} -F _n ）
F _{2n +1} = F _n ² + F _{n +1} ²

顺便说一句，实现非常紧凑。

比较不同方法的速度

just_maksim