费波纳奇记忆化的时间复杂度？

Time Complexity of Memoization Fibonacci?(费波纳奇记忆化的时间复杂度？)

问题描述

我有记忆斐波那契代码，我无法计算出它的时间复杂度是多少：

function fibMemo(index, cache) {
  cache = cache || [];
  if (cache[index]) return cache[index];
  else {
    if (index < 3) return 1;
    else {
      cache[index] = fibMemo(index - 1, cache) + fibMemo(index - 2, cache);
    }
  }

  return cache[index];
}

此函数的时间复杂度是多少？

推荐答案

取决于您的意思。

假设正确完成了备忘，则"操作"的数量将是生成的数字的数量。这意味着函数运行时与您试图生成的数字数量相关。

所以它将是O(N)，其中n是生成的数字的数量。

这篇关于费波纳奇记忆化的时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！