algorithm - 逆斐波那契算法？

Question

有许多计算任意 n 的 F(n) 的方法，其中许多方法具有很好的运行时间和内存使用率。

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

Given F(n) for n > 2, what is n?

(n > 2 限制在那里，因为 F(1) = F(2) = 1 并且没有明确的逆)。

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

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

Answer 1

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

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

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))。

实际算法需要两个步骤。

1. 计算 A^2、A^4、A^8 等，直到我们通过所需的数字。
2. 使用 A 的计算幂，按 n 进行二分查找。

附带说明，f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. 形式的任何序列+ kt*f(n-t) 可以这样表示。