Как рассчитать сложность рекурсивной функции?

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 состоит из всех N цифр 1 или 2.

Затем, если N для начала 20, то появятся еще два рекурсивных вызова N= 18 и N = 19,

Тогда N = 19 вызовет еще два вызова (и, таким образом, один, пока значение N не станет 0)

Таким образом, количество вызовов будет увеличиваться экспоненциально с каждой итерацией), следовательно, достигая значения (2^N - 1).