wake-up-neo.com

Beispiel eines faktoriellen Zeitalgorithmus O (n!)

Ich studiere Zeitkomplexität in der Schule, und unser Hauptfokus scheint auf Polynomialzeit O(n^c)-Algorithmen und quasi-lineare ZeitO(nlog(n))-Algorithmen zu liegen, mit dem gelegentlichen exponentiellen ZeitO(c^n)-Algorithmus als Beispiel Laufzeitperspektive. Der Umgang mit größeren zeitlichen Komplexitäten wurde jedoch nie abgedeckt.

Ich möchte ein Beispielproblem mit einer algorithmischen Lösung sehen, die in faktorieller Zeit O(n!) läuft. Der Algorithmus kann ein naiver Ansatz sein, um ein Problem zu lösen, kann jedoch nicht künstlich aufgebläht werden, um in faktorieller Zeit ausgeführt zu werden.

Zusätzliches Streetcredo, wenn der Faktorial Time-Algorithmus der bekannteste Algorithmus ist, um das Problem zu lösen.

algorithmcomplexity-theorytime-complexityfactorial
32
recursion.ninja

Generieren Sie alle Permutationen einer Liste

Sie haben n! Listen, so dass Sie keine bessere Effizienz als O(n!) erreichen können.

38
Ziyao Wei

Traveling Salesman hat eine naive Lösung, die O (n!) Ist, aber es hat eine dynamische Programmierlösung, die O (n ^ 2 * 2 ^ n) ist.

16
Zim-Zam O'Pootertoot

Alle Permutationen eines Arrays auflisten ist O (n!). Nachfolgend finden Sie eine rekursive Implementierung unter Verwendung der Swap-Methode. Die Rekursion befindet sich innerhalb der for-Schleife, und die Elemente im Array werden in Position getauscht, bis keine Elemente mehr vorhanden sind. Wie Sie anhand der Ergebniszählung sehen können, beträgt die Anzahl der Elemente im Array n !. Jede Permutation ist eine Operation und es gibt n! Operationen.

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!
5
archie

Hier ist ein einfaches Beispiel mit Big O (n!):

Dies ist in Python 3.4 

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