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

Ответ 1

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

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

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

Ответ 2

Когда вы выражаете сложность алгоритма, он всегда зависит от размера ввода. Допустимо только, что умножение является операцией 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!, а затем умножает все простые множители.

Ответ 3

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

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

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

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