Zeitkomplexitätsanalyse des Algorithmus

Question

Hallo Ich versuche, die Zeitkomplexität dieses Algorithmus zu analysieren, aber ich habe schwieriges Entwirren und Zählen, wie oft die letzte Schleife ausgeführt wird. Ich stelle fest, dass die erste Schleife log (n) ist, aber danach kann ich nicht zu einer Summe kommen, die gut auswertet. Hier ist der Algorithmus:

for(int i = 1; i <= n; i = 2*i){ 
    for(int j = 1; j <= i; j = 2*j){ 
     for(int k = 0; k <= j; k++){ 
      // Some elementary operation here. 
     } 
    } 
} 

Ich kann nicht herausfinden, wie oft die Schleife k führt im Allgemeinen w.r.t zu n

Vielen Dank für jede Hilfe!

Answer 1

Es ist O (n).

1 + 2 + 4 + ... + 2^N == 2^(N + 1) - 1.

der letzten Schleife für eine bestimmte j, j-mal ausführt.

Und für ein bestimmtes i, führen die inneren 2 Schleifen 1 + 2 + 4 + ... + i mal aus, was etwa 2 * i entspricht.

So ist die Gesamtausführungszeiten sind 1 * 2 + 2 * 2 + 4 * 2 + ... + N * 2, das etwa 4 * N. ist