Сложность рекурсивной факториальной программы
Какова сложность рекурсивной программы для нахождения факториала числа n? Моя догадка - то, что это могло бы быть O(n).
2 ответа
Если вы возьмете умножение как O (1) , тогда да, O (N) будет правильным. Однако обратите внимание, что умножение двух чисел произвольной длины x равно не O (1) на конечном оборудовании - поскольку x стремится к бесконечности, время, необходимое для умножения, увеличивается (например, если вы используете умножение Карацубы , это O (x ** 1,585) ).
Теоретически вы можете лучше справиться с достаточно большими числами с помощью Schönhage-Strassen , но, признаюсь, у меня нет реального опыта работы с этим. x , «длина» или «количество цифр» (в любом основании, не имеет значения для большого O в любом случае N, увеличивается с O (log N) , из конечно.
Если вы хотите ограничить свой вопрос факториалами чисел, достаточно короткими, чтобы их можно было умножить в O (1) , то N не может «стремиться к бесконечности» и поэтому запись с большим О неуместна.
Предполагая, что вы говорите о самом наивном факториальном алгоритме в истории:
factorial (n):
if (n = 0) then return 1
otherwise return n * factorial(n-1)
Да , алгоритм является линейным, выполняется за O (n) раз. Это так, потому что он выполняется один раз при каждом уменьшении значения n , и он уменьшает значение n , пока не достигнет 0 , что означает, что функция вызывается рекурсивно n раз. Это, конечно, предполагает, что и уменьшение, и умножение являются постоянными операциями.
Конечно, если вы реализуете факториал каким-либо другим способом (например, используя рекурсивное сложение вместо умножения), вы можете получить гораздо более сложный по времени алгоритм. Однако я бы не советовал использовать такой алгоритм.