Zeit Komplexität eines iterativen Algorithmus

Question

Ich versuche, die Zeit Komplexität dieser algorithm zu finden.

Der iterative: -Algorithmus erzeugt alle Bitstrings innerhalb einer gegebenen Hamming-Distanz, ausgehend von der eingegebenen Bitfolge. Er erzeugt alle ansteigenden Folgen 0 <= a[0] < ... < a[dist-1] < strlen(num) und setzt Bits bei entsprechenden Indizes zurück. Der Vektor a soll Indizes beibehalten, für die Bits invertiert werden müssen. Wenn also a den aktuellen Index i enthält, drucken wir 1 statt 0 und umgekehrt. Ansonsten drucken wir das Bit als (siehe else-Teil) ist, wie unten dargestellt:

// e.g. hamming("0000", 2); 
void hamming(const char* num, size_t dist) { 
    assert(dist > 0); 
    vector<int> a(dist); 
    size_t k = 0, n = strlen(num); 
    a[k] = -1; 
    while (true) 
     if (++a[k] >= n) 
      if (k == 0) 
       return; 
      else { 
       --k; 
       continue; 
      } 
     else 
      if (k == dist - 1) { 
       // this is an O(n) operation and will be called 
       // (n choose dist) times, in total. 
       print(num, a); 
      } 
      else { 
       a[k+1] = a[k]; 
       ++k; 
      } 
} 

Was ist die Zeitkomplexität dieses Algorithmus?

---

Mein Versuch, sagt:

dist * n + (n wählen t) * n + 2

aber dies scheint nicht wahr zu sein, die folgenden Beispiele betrachten, die alle mit dist = 2:

Hier sind zwei repräsentative Läufe (mit dem Druck, der am Sta geschehen soll) rt der Schleife):

000, len = 3 
k = 0, total_iter = 1 
vector a = -1 0 
k = 1, total_iter = 2 
vector a = 0 0 
Paid O(n) 
k = 1, total_iter = 3 
vector a = 0 1 
Paid O(n) 
k = 1, total_iter = 4 
vector a = 0 2 
k = 0, total_iter = 5 
vector a = 0 3 
k = 1, total_iter = 6 
vector a = 1 1 
Paid O(n) 
k = 1, total_iter = 7 
vector a = 1 2 
k = 0, total_iter = 8 
vector a = 1 3 
k = 1, total_iter = 9 
vector a = 2 2 
k = 0, total_iter = 10 
vector a = 2 3 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
gsamaras@pythagoras:~/Desktop/generate_bitStrings_HammDistanceT$ ./iter 
0000, len = 4 
k = 0, total_iter = 1 
vector a = -1 0 
k = 1, total_iter = 2 
vector a = 0 0 
Paid O(n) 
k = 1, total_iter = 3 
vector a = 0 1 
Paid O(n) 
k = 1, total_iter = 4 
vector a = 0 2 
Paid O(n) 
k = 1, total_iter = 5 
vector a = 0 3 
k = 0, total_iter = 6 
vector a = 0 4 
k = 1, total_iter = 7 
vector a = 1 1 
Paid O(n) 
k = 1, total_iter = 8 
vector a = 1 2 
Paid O(n) 
k = 1, total_iter = 9 
vector a = 1 3 
k = 0, total_iter = 10 
vector a = 1 4 
k = 1, total_iter = 11 
vector a = 2 2 
Paid O(n) 
k = 1, total_iter = 12 
vector a = 2 3 
k = 0, total_iter = 13 
vector a = 2 4 
k = 1, total_iter = 14 
vector a = 3 3 
k = 0, total_iter = 15 
vector a = 3 4 

Answer 1

Die while-Schleife etwas klug und subtil ist, und es ist fraglich, dass es zwei verschiedene Dinge tut (oder sogar drei, wenn Sie die Initialisierung von a zählen). Das ist es, was Ihre Berechnungen kompliziert macht, und es ist auch weniger effizient als es sein könnte.

In der Zusammenfassung, um schrittweise den nächsten Satzes von Indizes aus dem aktuellen Berechnung, die Idee, den letzten Index zu finden ist, i, das ist weniger als n-dist+i, es erhöht, und legen Sie die folgenden Indizes a[i]+1, a[i]+2, und so weiter.

Zum Beispiel, wenn dist = 5, n = 11 und die Indizes sind:

0, 3, 5, 9, 10 

Dann ist 5 der letzte Wert von weniger als n-dist+i (weil n-dist 6, und 10 = 6 + 4, 9 = 6 + 3, aber 5 < 6 + 2).

So erhöhen wir 5, und die nachfolgenden Zahlen stellen Sie den Satz von Indizes zu erhalten:

0, 3, 6, 7, 8 

Betrachten wir nun, wie Ihr Code ausgeführt wird, unter der Annahme, k=4

0, 3, 5, 9, 10 

• a[k] + 1 11 ist, so k wird 3.
• ++a[k] ist 10, also a[k+1] wird 10, und wird k 4.
• ++a[k] 11 ist, so wird k 3.
• ++a[k] 11 ist, so wird k 2.
• ++a[k] 6 ist, so wird a[k+1] 6 und k wird 3.
• ++a[k] 7, so a[k+1] wird 7 und k wird 4.
• ++a[k] 8 ist, und wir werden weiterhin die print Funktion aufzurufen.

Dieser Code ist richtig, aber es ist nicht effizient, weil k scuttles hin und her, wie es für den höchsten Index ist die Suche, das, ohne dass es einen Überlauf in dem höheren Indizes erhöht werden kann. Wenn der höchste Index vom Ende j ist, verwendet der Code eine nichtlineare Anzahl Iterationen der while-Schleife. Sie können dies einfach selbst demonstrieren, wenn Sie verfolgen, wie viele Iterationen der while-Schleife auftreten, wenn n==dist für verschiedene Werte von n. Es gibt genau eine Ausgabezeile, aber Sie sehen ein O (2^n) Wachstum in der Anzahl der Iterationen (tatsächlich werden Sie 2^(n + 1) -2 Iterationen sehen).

Dieses Versenken macht Ihren Code unnötig ineffizient und auch schwer zu analysieren.

void hamming2(const char* num, size_t dist) { 
    int a[dist]; 
    for (int i = 0; i < dist; i++) { 
     a[i] = i; 
    } 
    size_t n = strlen(num); 
    while (true) { 
     print(num, a); 
     int i; 
     for (i = dist - 1; i >= 0; i--) { 
      if (a[i] < n - dist + i) break; 
     } 
     if (i < 0) return; 
     a[i]++; 
     for (int j = i+1; j<dist; j++) a[j] = a[i] + j - i; 
    } 
} 

Nun, jedes Mal durch die while-Schleife erzeugt einen neuen Satz von Indizes:

Stattdessen können Sie den Code in einer direkteren Art und Weise schreiben. Die genauen Kosten pro Iteration sind nicht einfach, aber da print O (n) ist und der verbleibende Code in der while-Schleife im schlechtesten Fall O (dist) ist, sind die Gesamtkosten O (N_INCR_SEQ (n, dist) * n), wobei N_INCR_SEQ (n, dist) die Anzahl ansteigender Sequenzen von natürlichen Zahlen ist < n der Länge dist. Jemand in den Kommentaren stellt einen Link zur Verfügung, der eine Formel dafür liefert.

Answer 2

Hinweis, dass n gegeben, die die Länge repräsentiert und t die den Abstand erforderlich darstellt, um die Anzahl der steigenden, nicht negativer Reihe von t ganzen Zahlen zwischen 1 und n (oder in Indizes bilden, zwischen 0 und n-1) ist in der Tat n choose t, da wir t verschiedene Indizes auswählen.

das Problem bei der Erzeugung dieser Serie auftritt:

-First, dass 4 im Fall der Länge zum Beispiel feststellen, gehen Sie eigentlich über 5 verschiedene Indizes, 0 bis 4

-Zweitens Beachten Sie, dass Sie Konto-Serie mit identischen Indizes (im Fall von t=2, 0 0, 1 1, 2 2 und so weiter) nehmen, und im Allgemeinen würden Sie alle nicht-abnehmenden Serie statt durch jede zunehmende Serie gehen.

Also, um die TC Ihres Programms zu berechnen, stellen Sie sicher, dass Sie dies berücksichtigen.

Hinweis: versuchen Sie eine Eins-zu-eins-Entsprechung aus dem Universum dieser Reihen zu dem Universum der ganzzahligen Lösungen für eine Gleichung.

Wenn Sie die direkte Lösung benötigen, schauen Sie hier: https://math.stackexchange.com/questions/432496/number-of-non-decreasing-sequences-of-length-m

---

Die endgültige Lösung ist (n+t-1) choose (t), aber die erste Kugel zu bemerken, in Ihrem Programm, seine eigentlich ((n+1)+t-1) choose (t), da Sie Schleife mit einem zusätzlicher Index Bezeichnen

((n+1)+t-1) choose (t) =: A, n choose t =: B

Gesamt wir bekommen O(1) + B*O(n) + (A-B)*O(1)