时间戳

首页 > 解决方案 > 这个斐波那契实现的时间复杂度是多少？

javascript - 这个斐波那契实现的时间复杂度是多少？

问题描述

只是想知道是否有人可以解释这段代码背后的时间复杂度。谢谢！

function fib(N) {
  var arr = [0, 1, 1];
  for (i = 3; i <= N; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[N];
}

标签： javascriptloopstime-complexityfibonacci

解决方案

我们可以将代码拆分成几个部分，逐个分析。

var arr = [0, 1, 1];

这部分有O(1)，因为它甚至不依赖于 a N。

for (i = 3; i <= N; i++) {
  arr[i] = arr[i - 1] + arr[i - 2];
}

数组中的数字越多，从中获取两个元素所需的时间就越多，但是差异如此之小，以至于我们可以近似地将执行时间arr[i] = arr[i - 1] + arr[i - 2];视为常数。所以我们必须执行这段代码的次数是N. 这部分的时间复杂度是如此O(n)。

return arr[N];

arr[3]再次执行or之间的差异arr[10000000]可以忽略不计，因此每次的时间复杂度都是相同的O(1)。

这段代码的整体时间复杂度是部分复杂度中最大的部分，所以它是O(n).

推荐阅读