Пример алгоритма факториального времени O(n!)

Я изучаю временную сложность в школе, и наше основное внимание, похоже, сосредоточено на алгоритмах полиномиального времени O(n^c) и алгоритмах квазилинейного времени O(nlog(n)) с иногда экспоненциальным временем< /em> O(c^n) алгоритм как пример перспективы во время выполнения. Однако работа с большими временными сложностями никогда не рассматривалась.

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

Дополнительный уличный авторитет, если алгоритм факториального времени является наиболее известным алгоритмом для решения проблемы.


algorithm time-complexity factorial complexity-theory
person recursion.ninja    schedule 15.05.2013    source источник
comment
Поиск всех возможных путей от источника к месту назначения в ориентированном ациклическом графе (DAG).   -  person Keyur Potdar    schedule 24.07.2020

Ответы (4)


arrow_upward
56
arrow_downward

Сгенерировать все перестановки списка

У вас есть n! списки, поэтому вы не можете добиться большей эффективности, чем O(n!).

person zw324    schedule 15.05.2013
comment
@ziyao-wei Список всех комбинаций набора равен 2 ^ n. См.: en.wikipedia.org/wiki/ . Возможно, вы имеете в виду перечисление всех перестановок? т. е. учитывая n элементов, сколькими способами их можно упорядочить/переставить в строке n-длины? - person ChaimKut; 15.05.2014
comment
@ChaimKut: Странно, я действительно имел в виду перестановки, но спрашивающий изменил их на комбинации, согласно истории редактирования. Возвращение. - person zw324; 30.03.2015
comment
Это на самом деле не может быть лучше, чем O(n * n!), потому что у вас есть n! списков, и в каждом из них есть n вещей. - person btilly; 15.12.2020

arrow_upward
27
arrow_downward

У Коммивояжер есть простое решение, которое равно O(n!), но у него есть решение динамического программирования, которое О (п ^ 2 * 2 ^ п)

person Zim-Zam O'Pootertoot    schedule 15.05.2013

arrow_upward
6
arrow_downward

Список всех перестановок массива равен O(n!). Ниже представлена ​​рекурсивная реализация с использованием метода swap. Рекурсия находится внутри цикла for, и элементы в массиве меняются местами до тех пор, пока не останется элементов. Как видно из подсчета результатов, количество элементов в массиве равно n!. Каждая перестановка — это операция, и их n! операции.

def permutation(array, start, result)
    if (start == array.length) then
        result << array.dup  
    end
    for i in start..array.length-1 do
        array[start], array[i] = array[i], array[start]
        permutation(array, start+1,result)
        array[start], array[i] = array[i], array[start]
    end 
    result   
end        


p permutation([1,2,3], 0, []).count  #> 6 = 3!
p permutation([1,2,3,4], 0, []).count #> 24 = 4!
p permutation([1,2,3,4,5], 0, []).count #> 120 = 5!
person aarti    schedule 03.08.2015

arrow_upward
2
arrow_downward

Вот простой пример с Big O( n! ):

Это в питоне 3.4

 def factorial(n):
    for each in range(n):
        print(n)
        factorial(n-1)
person grepit    schedule 01.01.2019