Описание тега factorial

Описание тега Вопросы с тегом
В математике факториал неотрицательного целого числа n, обозначаемого n!, является произведением всех положительных целых чисел, меньших или равных n.

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

  • 5! = 5*4*3*2*1 = 120
  • 20! = 1*2*3*...*18*19*20 = 2 432 902008 176 640 000 (наибольший факториал, представимый как 64-битное длинное целое число)
  • 69! ≈ 1,72 × 1098, 70! ≈ 1,20 × 10100
  • 0! = 1 (по определению)

Факторная реализация

В компьютерном программировании функция, вычисляющая факториал числа, часто используется как пример рекурсивной функции. Вот простой рекурсивный код Python для функции факториала.

# Calculates factorial of a number n! recursively
def factorial(n):
    # Base case, stop when n is 0 or 1
    if n == 0 or n == 1:
        return 1
    # Recursive step
    return n*factorial(n-1)

Вот эквивалентная итерационная версия факториальной функции:

# Calculates factorial of a number n!
def factorial(n):
    # Base case, stop when n is 0 or 1
    if n == 0 or n == 1:
        return 1
    # Loop to multiply by successive integers
    product = 1
    counter = 2
    while counter <= n:
        product *= counter
        counter += 1
    return product

Применение факториала

Факториал важен в областях комбинаторики. Самый известный пример факториала - это подсчет способов, которыми n объектов могут быть расположены в строке - количество способов (перестановок) равно n!. Биномиальный коэффициент n Ck эквивалентен n!/к!(п-к)!. Он также играет роль в оценке степенных рядов хорошо известных функций, таких как exp.

Факторное время и сложность также являются одними из часто упоминаемых уровней сложности алгоритма, а именно сложности O(n!). Факториальная функция растет очень быстро и растет асимптотически быстрее, чем любая экспоненциальная функция an с линейной экспонентой, поэтому факториальное время и сложность указывают на очень плохую асимптотическую производительность. Фактически, 64-битное целое число может хранить только до 20!, и 69! является наибольшим факториалом меньше гугола.

Перечисление и создание списка всех перестановок n объектов требует факториального времени и пространства и быстро становится невозможным даже для небольших целых чисел, таких как 10.

Узнать больше