为给定的 n 找到斐波那契指数的时间复杂度

Question

这对我来说有点难以表达，但我很好奇如何计算迭代Fib(n)次的时间复杂度。

我有下面的一段代码，它将遍历斐波那契数列并从给定的输入中减去该数额。循环将运行 n 次，其中 n 为 Fib(n) > input.

代码的时间复杂度显然是Fib(n)，但是如何用Big-O表示法表示呢？

我在 math exchange 上读过这篇文章，如果我理解正确的话，它说时间复杂度是 O(n log phi) 或大约 O(1.618n)。所以 O(n)?

虽然感觉不对。

我还找到了（斐波那契公式）[http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#section6] 的其他资源，这个似乎说它实际上是：

i ≈ log( N ) + (log(5) / 2) / log(Phi)

上面感觉比较有道理

 public int findTheMaximumUsingALoop(int input) {
    if (input == 1 || input == 2) {
      return input;
    }

    int count = 2;

    int next = 1;
    int previous = 1;

    input -= next + previous;

    // loop until the next Fib number is more than we have left
    while (input > 0) {
      int tmp = previous;
      previous = next;
      next = next + tmp;

      input -= next;
      if (input >= 0) {
        count++;
      }
    }

    return count;
  }

Answer 1

数学交换 link 讨论的是 log(Fib(n)) 而非 Fib(n) 的渐近行为，因此无关紧要。

迭代 Fib(n) 次是指数运行次。您可以通过查看第 n 个斐波那契数的封闭式公式来了解这一点：（称为 Binet's formula）

增长为 O(phi ^ n)，其中 phi 为 (1 + sqrt(5))/2，大约为 1.618。

但是，您问题中的循环将不会迭代 O(Fibo(n)) 次。它将迭代 O(n) 次。它有运行次通过迭代计算第n个斐波那契数。

为给定的 n 找到斐波那契指数的时间复杂度

Time complexity of finding the Fibonacci index for a given n

fibonacci

time-complexity