Что такое Big O (сложность времени) для факторных вычислений?

Question

Это линейно для итеративной версии:

// O(n)
function factorial (n) {
  let ret = 1;
  for(let i = 2; i <= n; i++) {
    ret = ret * i;
  }
  return ret;
}

, и, по-видимому, линейно и для рекурсивной версии:

function factorialR (n) {
  if( n === 0 || n === 1 ) {
    return 1;
  } else {
    return n * factorialR(n - 1);
  }
}

Является ли линейным для рекурсивной версии как хорошо? Вместо al oop для каждого дополнительного значения это просто дополнительный вызов функции.

Answer 1

Обе ваши функции имеют O(n) сложность во времени.

Первая проста.

Вторая вызывает рекурсивную функцию один раз в каждой итерации, так что это также O(n).

Answer 2

Если ваш алгоритм рекурсивный с b рекурсивными вызовами на уровень и имеет L уровней, алгоритм имеет примерно O(b^L ) сложность

, но это только грубая верхняя граница. Фактическая сложность зависит от того, какие действия выполняются на уровне и возможно ли сокращение

Кредит: Стивен Халим

Для еще более сложной и сложной рекурсивной сложности времени перейдите к здесь