2^n Komplexität Algorithmus

Muss ich implementieren und testen Sie einen Algorithmus mit einer 2^n Komplexität. Ich habe versucht, einen zu finden für eine Weile. Wenn es irgendeinen Weg ich kann erreichen dies durch die Umsetzung-mit einer genauen Komplexität von 2^n, das wäre optimal. Wenn jemand weiß, von einem Ort kann ich ein Beispiel finden, oder könnte mir helfen umsetzen, das wäre genial :-). Die grundlegende Bedienung kann alles sein, aber ein einzelnes statment, wie i++; am besten wäre.

"Komplexität 2^n wäre die optimale" LOL
Ich habe einmal mit einem system, das hatte der Protokollierung umgesetzt in einer Weise, die das ganze system betreiben in O(n^n). Mir wurde gesagt, dass es war gut genug, dass die Anmeldung war es nicht möglich, die Auswirkungen einer Anwendung "nur loggen", aber berechnet, dass für die Verarbeitung der Daten festgelegt, die für die Kunden wurde ich gebeten, die Arbeit an, die ich brauchen würde etwa 6,4 Milliarden Jahren auf die hardware, die ich hatte. Ich schrieb eine SQL-Skript-generator und fertig in ein paar Stunden, habe auch einen Scheiße-Sturm nicht über das offizielle toolset. haaa gute'ol Erinnerungen !!
Vielleicht war es n!, Ich erinnere mich nicht genau
Dies ist eindeutig Hausaufgaben; das ist OK, aber bitte markieren Sie als solche. Danke.
Sind Sie sicher, es war nicht n^2? Ich kann mir nicht vorstellen, wie würden Sie log-in n^n Zeit.

InformationsquelleAutor rubixibuc | 2011-04-01

  1. 25

    Generieren aller Teilmengen einer Menge mit n Elementen.

    Hinzugefügt.
    Die einfachste Möglichkeit der Generierung aller Teilmengen von S = {a0, a1, ..., an-1} ist wahrscheinlich zu übersetzen zwischen der binären Darstellung der Rang-und der Teilmenge.

    Nehmen Sie die S = {a0, a1, a2}.

    rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

    So, eine 1 in der binären bedeutet das entsprechende element in der Teilmenge. Eine 0 bedeutet, dass das element nicht im subset.

    Aber Sie sollten auch lookup-Gray-code.

    Danke 🙂 Das ist perfekt, weißt du, wo finde ich eine Beispiel-Implementierung dieser?
    oder wie darf ich das genau implementieren Sie die Steuerelemente Struktur und nur ich++ für die Erklärung.
    Ich bin nur gonna vote Sie nach oben und unten zu sehen, die Einhörner tanzen.
    Mal sehen, die pseudo-code

    InformationsquelleAutor user515430

  2. 8

    Die klassische rekursive Fibonacci-Zahl-Berechnung ist O(2^n).

    unsigned Fib(unsigned n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

    Da oben ist eigentlich theta(Phi^n), ich bin das hinzufügen einer theta(2^n) - Algorithmus, der die Rückkehr 2^n ist. Dank Jeremia Willcock.

    unsigned TwoExp(unsigned n)
{
    if (n == 0)
        return 1;
    else
        return TwoExp(n - 1) + TwoExp(n - 1);
}
    Ist es nicht nur O(Fib(n)), welche nur etwa 1,6^n? Wenn Sie ersetzt Fib(n - 2) durch Fib(n - 1) unten, obwohl, wäre es 2^n ist.
    ja, technisch gesehen ist dieser Algorithmus, theta(Phi^n), der in O(2^n). (Phi = (5^(1/2) + 1) / 2, über 1.61.

    InformationsquelleAutor ThomasMcLeod

  3. 4

    Quantum Bogosort hat 2^n Speicherplatz-Komplexität.

    Ziemlich sicher, es hat n! Raum Komplexität.

    InformationsquelleAutor wilhelmtell

  4. 1

    Hier ist einer: Ausgabe der Ziffern von 2^(2^n).

    InformationsquelleAutor wnoise

  5. 1

    Verbrachte ich sehr viel Zeit, überdenken Sie das problem und möchte nach einer Lösung kam ich mit. Alle Antworten dazu beigetragen, meine Fähigkeit zu kommen mit dieser Lösung und bin sehr dankbar für alle, die reponded. 🙂 Ich merke, dass der Algorithmus tut praktisch nichts.

    es ist in java geschrieben

    kann nicht scheinen, um die Registerkarten, um die Arbeit

    die grundlegende Bedienung ist i++; 

    public class TwoToTheN
{  
     private static int twoToTheN = 0;  
     private static int power = 3;

     public static void main(String[] args)   
     {  
         twoToTheN(power);  
         System.out.println(twoToTheN);  
     }  

     private static void twoToTheN(int n)  
     {  
         if(n == 0)   
         {  
             twoToTheN++;  
             return;  
         } 
         else if(n == 1)  
         {  
             twoToTheN++;  
             twoToTheN++;  
             return;  
         }  
         twoToTheN(n-1);  
         twoToTheN(n-1);  
     }
}

    InformationsquelleAutor rubixibuc

Schreibe einen Kommentar