如何计算递归函数的复杂度？

Question

计算以下递归函数的时间和space复杂度（大 O 表示法）的最直观方法是什么？

function count(str) {
  if (str.length <= 1) {
    return 1;
  }

  var firstTwoDigits = parseInt(str.slice(0, 2), 10);

  if (firstTwoDigits <= 26) {
    return count(str.slice(1)) +
           count(str.slice(2));
  }

  return count(str.slice(1));
}

Answer 1

对我之前的回答表示歉意，您的代码似乎很复杂

O(2^N) 或 O(2^N-1) 准确地说是在最坏的情况下。

所以，如果

N = str.length ;//number of iteration

在最坏的情况下，您的 str 由所有 N 位 1 或 2 组成。

然后，如果 N 一开始是 20，那么它会产生两个递归调用 N= 18 和 N = 19,

然后，N = 19 将产生另外两个调用（直到 N 的值为 0 ）

因此，调用次数将随着每次迭代呈指数增长），因此达到值 (2^N - 1)。

如何计算递归函数的复杂度？

How to calculate the complexity of a recursive function?

javascript

recursion

complexity-theory

big-o