Beispiel für O (n!)?

Question

Was ist ein Beispiel (im Code) einer O (n!) - Funktion? Es sollte eine angemessene Anzahl von Operationen in Bezug auf n ausführen; das heißt, ich frage nach Zeitkomplexität.

Answer 1

Dort gehen Sie. Dies ist wahrscheinlich das am meisten triviale Beispiel einer Funktion, die in O(n!) Zeit abläuft (wobei n ist das Argument der Funktion):

void nFacRuntimeFunc(int n) { 
    for(int i=0; i<n; i++) { 
    nFacRuntimeFunc(n-1); 
    } 
} 

Answer 2

Ein klassisches Beispiel ist die traveling salesman problem durch Brute-Force-Suche.

Wenn es N Städte sind, wird die Brute-Force-Methode versuchen, jede einzelne Permutation dieser N Städte zu finden, die man am billigsten ist. Jetzt ist die Anzahl der Permutationen mit N Städten N! macht es factorial factory (O(N!)).

Answer 3

das einfachste Beispiel :)

Pseudo-Code:

input N 
calculate N! and store the value in a vaiable NFac - this operation is o(N) 
loop from 1 to NFac and output the letter 'z' - this is O(N!) 

da gehst du :)

Als ein echtes Beispiel - was ist mit dem Generieren aller Permutationen einer Reihe von Elementen?

Answer 4

Finden der Determinante mit der Erweiterung durch Minderjährige.

Sehr gute Erklärung here.

# include <cppad/cppad.hpp> 
# include <cppad/speed/det_by_minor.hpp> 

bool det_by_minor() 
{ bool ok = true; 

    // dimension of the matrix 
    size_t n = 3; 

    // construct the determinat object 
    CppAD::det_by_minor<double> Det(n); 

    double a[] = { 
     1., 2., 3., // a[0] a[1] a[2] 
     3., 2., 1., // a[3] a[4] a[5] 
     2., 1., 2. // a[6] a[7] a[8] 
    }; 
    CPPAD_TEST_VECTOR<double> A(9); 
    size_t i; 
    for(i = 0; i < 9; i++) 
     A[i] = a[i]; 


    // evaluate the determinant 
    double det = Det(A); 

    double check; 
    check = a[0]*(a[4]*a[8] - a[5]*a[7]) 
      - a[1]*(a[3]*a[8] - a[5]*a[6]) 
      + a[2]*(a[3]*a[7] - a[4]*a[6]); 

    ok = det == check; 

    return ok; 
} 

Code von here. Sie finden auch die notwendigen .hpp Dateien there.

Answer 5

Es gibt Probleme, die sind NP-complete (in nichtdeterministischen polynomialen Zeit nachweisbar). Wenn die Eingabe skaliert wird, erhöht sich die Anzahl der Berechnungen, die zur Lösung des Problems benötigt werden.

Einige NP-hard Probleme sind: Hamiltonian path problem ( open img), Travelling salesman problem ( open img)
Einige NP-complete Probleme sind: Boolean satisfiability problem (Sat.) ( open img), N-puzzle ( open img), Knapsack problem ( open img), Subgraph isomorphism problem ( open img), Subset sum problem ( open img), Clique problem ( open img), Vertex cover problem ( open img), Independent set problem ( open img), Dominating set problem ( open img), Graph coloring problem ( open img),

Quelle: link 1, link 2

Quelle: link

Answer 6

Siehe Orders of common functions Abschnitt des Big O Wikipedia Artikels.

Nach dem Artikel, die Lösung traveling salesman problem über Brute-Force-Suche und das Finden der determinant mit expansion by minors sind beide O (n!).

Answer 7

In Wikipedia

das Reiseproblem über Brute-Force-Methode lösen; Finden der Determinante mit der Erweiterung durch Minderjährige.

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

Answer 8

Bogosort ist der einzige "offizielle", die ich, dass Unternehmungen in die O begegnet sind (n!) Bereich. Aber es ist kein garantiertes O (n!), Da es zufällig ist.

Answer 9

Ich denke, ich bin ein bisschen spät, aber ich finde snailsort, um das beste Beispiel für O (n!) Deterministischen Algorithmus zu sein. Es findet im Grunde die nächste Permutation eines Arrays, bis es es sortiert.

Es sieht wie folgt aus:

template <class Iter> 
void snail_sort(Iter first, Iter last) 
{ 
    while (next_permutation(first, last)) {} 
} 

Answer 10

Die rekursive Methode, die Sie wahrscheinlich für die Aufnahme der Determinante einer Matrix gelernt (wenn man lineare Algebra hat) nimmt O (n!) Zeit. Obwohl ich nicht besonders Lust habe, alles zu programmieren.

Answer 11

Jeder Algorithmus, der die gesamte Permutation eines gegebenen Arrays berechnet, ist O (N!).

Answer 12

In C#

Wäre das nicht O (N!) Seine im Raum Komplexität? weil String in C# unveränderlich ist.

string reverseString(string orgString) { 
    string reversedString = String.Empty; 

    for (int i = 0; i < orgString.Length; i++) { 
     reversedString += orgString[i]; 
    } 

    return reversedString; 
} 

Answer 13

printf("Hello World");

Ja, das ist O (n!). Wenn Sie denken, dass es nicht ist, schlage ich vor, dass Sie die Definition von BigOh lesen.

Ich habe diese Antwort nur wegen der lästigen Gewohnheit hinzugefügt, die Leute immer BigOh benutzen müssen, egal was sie eigentlich meinen.

Zum Beispiel bin ich ziemlich sicher, dass die Frage Theta (n!), Zumindest cn fragen sollte! Schritte und nicht mehr als Cn! Schritte für einige Konstanten c, C> 0, aber wählte stattdessen O (n!).

Eine andere Instanz: Quicksort is O(n^2) in the worst case, während technisch korrekt (Selbst Heapsort ist O (n^2 im schlimmsten Fall!), Was sie eigentlich bedeuten ist Quicksort is Omega(n^2) in the worst case.

Answer 14

@clocksmith Sie sind absolut richtig. Dies berechnet nicht n !. Es ist auch nicht von O (n!). Ich habe es die Daten in der Tabelle unten gesammelt. Bitte vergleichen Sie Spalte 2 und 3. (#nF ist die Anzahl der Aufrufe von nFacRuntimeFunc)

n #nF n!

0 0  1 
1 1  1 
2 4  2 
3 15  6 
4 65  24 
5 325 120 
6 1956 720 
7 13699 5040 

Also klar, wenn viel schlechter als O (n!) Führt. Unten ist der Beispielcode für die Berechnung von n! rekursiv. Sie werden feststellen, dass es von O (n) ist.

int Factorial(int n) 
{ 
    if (n == 1) 
     return 1; 
    else 
     return n * Factorial(n-1); 
} 

Answer 15

Sie haben Recht, die rekursiven Aufrufe sollten genau n dauern! Zeit. Hier ist ein Code wie faktorielle Zeit für n verschiedene Werte zu testen. Innere Schleife läuft für n!Zeit für verschiedene Werte von j, so die Komplexität der inneren Schleife ist Big O (n!)

public static void NFactorialRuntime(int n) 
    { 
     Console.WriteLine(" N Fn N!"); 
     for (int i = 1; i <= n; i++) // This loop is just to test n different values 
     { 
      int f = Fact(i); 
      for (int j = 1; j <= f; j++) // This is Factorial times 
      { ++x; } 
      Console.WriteLine(" {0} {1} {2}", i, x, f); 
      x = 0; 
     } 
    } 

Hier sind die Testergebnis für n = 5, iterieren es genau faktorielles Zeit.

N Fn N! 
    1 1 1 
    2 2 2 
    3 6 6 
    4 24 24 
    5 120 120 

Exakte Funktion mit zeitlicher Komplexität n!

// Big O(n!) 
public static void NFactorialRuntime(int n) 
    { 
     for (int j = 1; j <= Fact(i); j++) { ++x; } 
     Console.WriteLine(" {0} {1} {2}", i, x, f); 
    }