Сложность рекурсивной факториальной программы

Если вы принимаете умножение как O(1), то да, O(N) правильно. Однако обратите внимание, что умножение двух чисел произвольной длины x не O(1) на конечном оборудовании — поскольку x стремится к бесконечности, время, необходимое для умножения, увеличивается (например, если вы используете умножение Карацубы, это O(x ** 1.585)).

Теоретически вы можете добиться большего успеха для достаточно больших чисел с Schönhage-Strassen, но Признаюсь, у меня нет реального опыта работы с этим. x, «длина» или «количество цифр» (в любом основании, не имеет значения для большого-0 в любом случае N, растет с O(log N), конечно.

Если вы хотите ограничить свой вопрос факториалами чисел, достаточно короткими, чтобы их можно было умножить на O(1), то N никак не может «стремиться к бесконечности», и поэтому обозначение big-O неуместно.

Предполагая, что вы говорите о самом наивном факториальном алгоритме:

factorial (n):
  if (n = 0) then return 1
  otherwise return n * factorial(n-1)

Да, алгоритм линейный, работает за время O(n). Дело в том, что она выполняется один раз каждый раз, когда уменьшает значение n, и уменьшает значение n, пока не достигнет 0, то есть функция вызывается рекурсивно n раз. Это предполагает, конечно, что и декрементация, и умножение являются постоянными операциями.

Конечно, если вы реализуете факториал каким-то другим способом (например, используя рекурсивное сложение вместо умножения), вы можете получить гораздо более сложный по времени алгоритм. Однако я бы не советовал использовать такой алгоритм.

Когда вы выражаете сложность алгоритма, она всегда зависит от размера входных данных. Можно предположить, что умножение является операцией O(1), только если числа, которые вы умножаете, имеют фиксированный размер. Например, если вы хотите определить сложность алгоритма, вычисляющего произведения матриц, вы можете предположить, что отдельные компоненты матриц имеют фиксированный размер. Тогда было бы правильно предположить, что умножение двух отдельных компонентов матрицы равно O(1), и вы должны вычислить сложность в соответствии с количеством элементов в каждой матрице.

Однако, когда вы хотите вычислить сложность алгоритма вычисления N!, вы должны предположить, что N может быть сколь угодно большим, поэтому неверно предполагать, что умножение является операцией O(1).

Если вы хотите умножить n-битное число на m-битное число, наивный алгоритм (тот, который вы делаете вручную) требует времени O(mn), но есть более быстрые алгоритмы.

Если вы хотите проанализировать сложность простого алгоритма вычисления N!

    factorial(N)
       f=1
       for i = 2 to N
          f=f*i

       return f

затем на k-м шаге цикла for вы умножаете (k-1)! на k. Количество битов, используемых для представления (k-1)!, равно O(k log k), а количество битов, используемых для представления k, равно O(log k). Таким образом, время, необходимое для умножения (k-1)! и k, равно O(k (log k)^2) (при условии, что вы используете наивный алгоритм умножения). Тогда общее время, затрачиваемое алгоритмом, равно сумме времени, затраченного на каждый шаг:

sum k = 1 to N [k (log k)^2] <= (log N)^2 * (sum k = 1 to N [k]) =
O(N^2 (log N)^2)

Вы можете улучшить эту производительность, используя более быстрый алгоритм умножения, такой как Schönhage-Strassen, который занимает время O(n*log(n)*log(log(n))) для 2 n-битных чисел.

Другой способ повысить производительность — использовать более совершенный алгоритм для вычисления N!. Самый быстрый из тех, что я знаю, сначала вычисляет простую факторизацию числа N!, а затем перемножает все простые множители.

Временная сложность рекурсивного факториала будет:

factorial (n) {    
    if (n = 0) 
        return 1
    else
        return n * factorial(n-1)
}

So,

Временная сложность для одного рекурсивного вызова будет:

T(n) = T(n-1) + 3   (3 is for As we have to do three constant operations like 
                 multiplication,subtraction and checking the value of n in each recursive 
                 call)

     = T(n-2) + 6  (Second recursive call)
     = T(n-3) + 9  (Third recursive call)
     .
     .
     .
     .
     = T(n-k) + 3k
     till, k = n

     Then,

     = T(n-n) + 3n
     = T(0) + 3n
     = 1 + 3n

Чтобы представить в нотации Big-Oh,

T(N) прямо пропорциональна n,

Следовательно, временная сложность рекурсивного факториала составляет O (n). Поскольку во время рекурсивных вызовов не требуется дополнительное пространство, сложность пространства составляет O (N).