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

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

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是生成的数字的数量。