Beispiel für O (n!)?

Dort gehen Sie. Dies ist wahrscheinlich das einfachste Beispiel einer Funktion, die ausgeführt wird in O(n!) Zeit (wo n ist das argument der Funktion):

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

InformationsquelleAutor der Antwort sepp2k

Sehen die Bestellungen von gemeinsamen Funktionen Abschnitt der Big O Wikipedia Artikel.

Laut dem Artikel, der Lösung des traveling salesman problem via brute-force-Suche und finden Sie die Determinante mit expansion durch Minderjährige sind beide O(n!).

InformationsquelleAutor der Antwort Bill the Lizard

Finden der Determinante mit der Erweiterung durch Minderjährige an.

Sehr gute Erklärung hier.

# 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 hier. Dort finden Sie auch die notwendigen .hpp Dateien dort.

InformationsquelleAutor der Antwort Jungle Hunter

das einfachste Beispiel 🙂

pseudocode:

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!)

dort gehen Sie 🙂

Als ein echtes Beispiel - was zur Erzeugung aller Permutationen einer Gruppe von Elementen?

InformationsquelleAutor der Antwort Armen Tsirunyan

printf("Hello World");

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

Ich nur Hinzugefügt, diese Antwort, weil Sie die lästige Angewohnheit haben Menschen immer BigOh unabhängig davon, was Sie eigentlich bedeuten.

Zum Beispiel, ich bin ziemlich sicher, dass die Frage bestimmt zu Fragen, Theta(n!), mindestens cn! Schritte und nicht mehr als Cn. Schritte für einige Konstanten c, C > 0, aber entschied sich zur Verwendung von O(n!) statt.

Andere Instanz: Quicksort is O(n^2) in the worst casezwar technisch korrekt (Sogar heapsort ist O(n^2) im worst-case!), was Sie tatsächlich bedeuten, ist Quicksort is Omega(n^2) in the worst case.

InformationsquelleAutor der Antwort

In C#

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

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

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

    return reversedString;
}

InformationsquelleAutor der Antwort user623429

Den rekursiven Methode, die Sie wahrscheinlich gelernt, für die die Determinante der matrix (wenn Sie nahm die lineare algebra) in O(n!) Zeit. Obwohl ich nicht besonders Lust-Kodierung, die alle bis.

InformationsquelleAutor der Antwort user477556

Du hast Recht die rekursiven Aufrufe sollten genau n! Zeit. hier ist ein code gerne testen faktorielle Zeit für n verschiedene Werte. Die innere Schleife läuft für n! Zeit für verschiedene Werte von j, so dass die Komplexität der inneren Schleife ist der Große 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 test-Resultat für n = 5, Sie Durchlaufen genau die Faktoren-Zeit.

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

Genaue Funktion mit Zeit-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);
    }

InformationsquelleAutor der Antwort techdips