Voorbeeld van O(n!)?

Wat is een voorbeeld (in code) van een functie O(N!)? Het moet het juiste aantal bewerkingen vergen om te worden uitgevoerd met verwijzing naar N; dat wil zeggen, ik vraag naar de complexiteit van de tijd.


Antwoord 1, autoriteit 100%

Daar ga je. Dit is waarschijnlijk het meest triviale voorbeeld van een functie die wordt uitgevoerd in O(N!)tijd (waarbij Nhet argument voor de functie is):

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

Antwoord 2, autoriteit 42%

Een klassiek voorbeeld is het probleem met reizende verkopersvia brute-force zoeken.

Als er Nsteden zijn, zal de brute force-methode elke permutatie van deze Nsteden proberen om uit te vinden welke het goedkoopst is. Nu is het aantal permutaties met Nsteden N!waardoor het complexiteitsfactorieel is (O(N!)).


Antwoord 3, autoriteit 9%

Zie het gedeelte Orders van algemene functiesvan het Big O Wikipediaartikel.

Volgens het artikel, het oplossen van het probleem met reizende verkopersvia brute-force zoeken en het vinden van de determinantmet uitbreiding met minderjarigenzijn beide O(n!).


Antwoord 4, autoriteit 5%

Ik denk dat ik een beetje laat ben, maar ik vind snailsorthet beste voorbeeld te zijn van een O(n!) deterministisch algoritme. Het vindt in feite de volgende permutatie van een array totdat het deze sorteert.

Het ziet er zo uit:

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

Antwoord 5, autoriteit 5%

Elk algoritme dat alle permutaties van een gegeven array berekent, is O(N!).


Antwoord 6, autoriteit 4%

Determinant vinden met uitbreiding door minderjarigen.

Zeer goede uitleg 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 van hier. U vindt daar ook de benodigde .hpp-bestanden daar .


Antwoord 7, autoriteit 4%

Het eenvoudigste voorbeeld 🙂

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

Daar ga je 🙂

Als een echt voorbeeld – hoe zit het met het genereren van alle permutaties van een reeks items?


8, Autoriteit 2%

in wikipedia

Het probleem van de reizende verkoper oplossen via Brute-Force Search; het vinden van de determinant met expansie door minderjarigen.

http://en.wikipedia.org/wiki/big_o_notation#orders_of_common_functions


9

printf("Hello World");

Ja, dit is o (n!). Als u denkt dat het niet is, stel ik aan dat u de definitie van BIGOH leest.

Ik heb dit antwoord alleen toegevoegd vanwege de irritante gewoonte die mensen altijd bigoh moeten gebruiken, ongeacht wat ze eigenlijk betekenen.

Ik ben bijvoorbeeld vrij zeker van de vraag die bedoeld is om THETA (N!), tenminste CN! stappen en niet meer dan CN! Stappen voor sommige constanten C, C & GT; 0, maar koos ervoor om in plaats daarvan o (n!) Te gebruiken.

Nog een instantie: Quicksort is O(n^2) in the worst case, terwijl technisch correct is (zelfs hopen is o (n ^ 2) in het ergste geval!), wat ze eigenlijk betekenen is Quicksort is Omega(n^2) in the worst case.


10

in c #

Zou dit niet o (n!) in de ruimtecomplexiteit zijn? omdat, string in C # is onveranderlijk.

string reverseString(string orgString) {
    string reversedString = String.Empty;
    for (int i = 0; i < orgString.Length; i++) {
        reversedString += orgString[i];
    }
    return reversedString;
}

Antwoord 11

Je hebt gelijk, de recursieve oproepen moeten precies n hebben! tijd. hier is een code om de faculteitstijd te testen voor n verschillende waarden. Binnenlus loopt voor n! tijd voor verschillende waarden van j, dus de complexiteit van de binnenste lus is 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 zijn de testresultaten voor n = 5, het herhaalt exact de tijd van de faculteit.

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

Exacte functie met tijdcomplexiteit 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);
    }

Antwoord 12

Bogosortis de enige “officiële” die ik ben tegengekomen die zich in de O( n!) gebied. Maar het is geen gegarandeerde O(n!) omdat het willekeurig van aard is.


Antwoord 13

De recursieve methode die je waarschijnlijk hebt geleerd voor het nemen van de determinant van een matrix (als je lineaire algebra hebt gebruikt) kost O(n!) tijd. Hoewel ik niet echt zin heb om dat allemaal te coderen.


Antwoord 14

@clocksmith Je hebt helemaal gelijk. Dit is geen berekening van n!. Het is ook niet van O(n!). Ik heb het uitgevoerd, verzamelde de gegevens in de onderstaande tabel. Vergelijk kolom 2 en drie. (#nF is het aantal aanroepen naar 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

Dus duidelijk als het veel slechter presteert dan O(n!). Hieronder vindt u een voorbeeldcode voor het berekenen van n! recursief. je zult merken dat het van O(n) orde is.

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

Antwoord 15

Toevoegen aan functie k

Dit is een eenvoudig voorbeeld van een functie met complexiteit O(n!) gegeven een array van int in parameter en een geheel getal k. het geeft true terug als er twee items uit de array zijn x+y = k , Bijvoorbeeld: als tab [1, 2, 3, 4] en k=6 was, zou de geretourneerde waarde waar zijn omdat 2+4=6

public boolean addToUpK(int[] tab, int k) {
        boolean response = false;
        for(int i=0; i<tab.length; i++) {
            for(int j=i+1; j<tab.length; j++) {
                if(tab[i]+tab[j]==k) {
                    return true;
                }
            }
        }
        return response;
    }

Als bonus is dit een eenheidstest met jUnit, het werkt prima

@Test
    public void testAddToUpK() {
        DailyCodingProblem daProblem = new DailyCodingProblemImpl();
        int tab[] = {10, 15, 3, 7};
        int k = 17;
        boolean result = true; //expected result because 10+7=17
        assertTrue("expected value is true", daProblem.addToUpK(tab, k) == result);
        k = 50;
        result = false; //expected value because there's any two numbers from the list add up to 50
        assertTrue("expected value is false", daProblem.addToUpK(tab, k) == result);
    }

Other episodes