计算任意n的F（n）的方法有很多种，其中许多具有很大的运行时和内存使用率。
但是，假设我想问相反的问题：
给定n> 2的F（n），n是多少？
（因为F（1）= F（2）= 1且没有明确的逆，所以存在n> 2限制）。
解决这个问题的最有效方法是什么？通过枚举斐波纳契数并在达到目标数时停止，可以很容易地在线性时间内做到这一点，但是有什么方法可以比那更快吗？
编辑： 当前，此处发布的最佳解决方案使用O（log n）内存在O（log n）时间运行，假设数学运算在O（1）中运行并且一个机器字可以在O（1）空间中容纳任何数字。我很好奇是否有可能降低内存需求，因为您可以使用O（1）空间计算斐波那契数。
由于OP询问的矩阵解决方案不涉及任何浮点计算，因此就在这里。O(logn)假设数值运算具有O(1)复杂性，我们可以通过这种方式实现复杂性。
O(logn)
O(1)
让我们以A具有以下结构的2x2矩阵为例
A
1 1 1 0
现在考虑vector (8, 5)，存储两个连续的斐波那契数。如果将其乘以该矩阵，将得到(8*1 + 5*1, 8*1 + 5*0) = (13, 8)-下一个斐波那契数。 如果我们概括一下A^n * (1, 0) = (f(n), f(n - 1))。
(8, 5)
(8*1 + 5*1, 8*1 + 5*0) = (13, 8)
A^n * (1, 0) = (f(n), f(n - 1))
实际算法需要两个步骤。
A^2
A^4
A^8
n
顺便说一句，f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)可以像这样显示表格的任何顺序。
f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t)
