time-complexity - 查找给定 n 的斐波那契指数的时间复杂度

Question

这对我来说有点难以用语言表达，但我很想知道如何计算迭代Fib(n)时间的时间复杂度。

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

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

我在数学交流中读过这篇文章，如果我理解正确的话，时间复杂度是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;
  }

标签： time-complexityfibonacci

Answer 1

该数学交换链接正在谈论 log(Fib(n)) 而不是 Fib(n) 的渐近行为，因此不相关。

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

O(phi ^ n)它像phi一样增长(1 + sqrt(5))/2，大约为 1.618。

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