fibonacci - 为什么这个斐波那契数函数在 O(log N) 中不起作用？

Question

所以 log (N) 的斐波那契数 - 没有矩阵。

Ni // i-th Fibonacci number
= Ni-1 + Ni-2              // by definition
= (Ni-2 + Ni-3) + Ni-2     // unwrap Ni-1
= 2*Ni-2 + Ni-3            // reduce the equation
= 2*(Ni-3 + Ni-4) + Ni-3   //unwrap Ni-2
                           // And so on
= 3*Ni-3 + 2*Ni-4
= 5*Ni-4 + 3*Ni-5
= 8*Ni-5 + 5*Ni-6

= Nk*Ni-k + Nk-1*Ni-k-1

现在我们编写一个递归函数，其中每一步都采用 k~=I/2。

static long N(long i)
{
    if (i < 2) return 1;
    long k=i/2;
    return N(k) * N(i - k) + N(k - 1) * N(i - k - 1);
}

哪里出了问题？

Answer 1

您将得到该工作量的递归公式:T(n) = 4T(n/2) + O(1)。 (忽略数字变大的事实，因此 O(1) 甚至不成立)。由此可见，T(n) 不在 O(log(n)) 范围内。相反，我们可以通过主定理 T(n) 得到 O(n^2)。

顺便说一句，这比计算 n 以内的所有斐波那契数的简单算法还要慢。