如何计算递归函数的复杂性

Question

计算以下递归函数的时空复杂度（Big 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由 1 或 2 的所有 N 位数字组成。

然后，如果 N 一开始是 20，那么它将生成另外两个递归调用 N= 18 和 N = 19，

然后，N = 19 将再生成两个调用（因此一个直到 N 的值为 0）

因此

，调用次数将随着每次迭代呈指数级增长），因此得出值 （2^N - 1）。