逆斐波那契算法?

问题描述

有数十种方法可以计算任意n的F(n)，其中许多方法具有很高的运行时和内存使用率.

There are dozens of ways of computing F(n) for an arbitrary n, many of which have great runtime and memory usage.

但是，假设我想问相反的问题:

However, suppose I wanted to ask the opposite question:

(因为F(1)= F(2)= 1且没有明确的逆，所以n> 2的限制在其中.)

(The n > 2 restriction is in there since F(1) = F(2) = 1 and there's no unambiguous inverse).

解决此问题的最有效方法是什么?通过枚举斐波那契数并在达到目标数时停止，可以很容易地在线性时间内做到这一点，但是有什么方法可以比那更快吗?

What would be the most efficient way of solving this problem? It's easy to do this in linear time by enumerating the Fibonacci numbers and stopping when you hit the target number, but is there some way of doing this any faster than that?

编辑:当前，此处发布的最佳解决方案是使用O(log n)内存在O(log n)时间运行，假设数学运算在O(1)中运行并且一个机器字可以在O(1)空间中容纳任意数字.我很好奇是否有可能降低内存需求，因为您可以使用O(1)空间计算斐波那契数.

currently, the best solution posted here runs in O(log n) time using O(log n) memory, assuming that mathematical operations run in O(1) and that a machine word can hold any number in O(1) space. I'm curious if it's possible to drop the memory requirements, since you can compute Fibonacci numbers using O(1) space.

推荐答案

由于OP询问了不涉及任何浮点计算的矩阵解决方案，所以就在这里.假设数值运算具有O(1)复杂度，我们可以通过这种方式实现O(logn)复杂度.

Since OP has asked about matrix solution not involving any floating point computations, here it is. We can achieve O(logn) complexity this way, assuming numeric operations have O(1) complexity.

让我们采用具有以下结构的2x2矩阵A

Let's take 2x2 matrix A having following structure

1 1
1 0

现在考虑向量(8, 5)，该向量存储两个连续的斐波那契数.如果将其乘以该矩阵，将得到(8*1 + 5*1, 8*1 + 5*0) = (13, 8)-下一个斐波那契数.
如果我们概括一下，请A^n * (1, 0) = (f(n), f(n - 1)).

Now consider vector (8, 5), storing two consecutive fibonacci numbers. If you multiply it by this matrix, you'll get (8*1 + 5*1, 8*1 + 5*0) = (13, 8) - the next fibonacci number.
If we generalize, A^n * (1, 0) = (f(n), f(n - 1)).

实际算法需要两个步骤.

The actual algorithm takes two steps.

1. 计算A^2，A^4，A^8等，直到我们通过所需的数字为止.
2. 使用计算出的A的幂，通过n进行二进制搜索.

1. Calculate A^2, A^4, A^8, etc. until we pass desired number.
2. Do a binary search by n, using calculated powers of A.

在旁注中，任何形式为f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)的序列都可以这样显示.

On a side note, any sequence of the form f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t) can be presented like this.

这篇关于逆斐波那契算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！