Komplexität für eine verschachtelte Schleife mit wachsender innerer Schleife

Question

Ich bin verwirrt über die Zeitkomplexität dieses Code-Abschnitts und die Logik, die verwendet wurde, um sie zu finden.

void doit(int N) {
    for (int k = 1; k < N; k *= 2) { <----Ich vermute, dass dies O(logN) ist
           for (int j = 1; j < k; j += 1) { <------Ich bin mir nicht sicher, wie dieser Teil funktioniert.
       }
    }
}

Ich habe bereits versucht, es mit der Hand auszuarbeiten. Aber ich verstehe es immer noch nicht.

Danke für Ihre Zeit.

EDIT:

Ich füge eine weitere Frage hinzu. Dasselbe Konzept, aber im anderen Format.

void doit(int N) {
    int j, k; //Am Ende kam ich auf die Antwort O(n^(n/2)). Aber dann war ich danach stecken...ist das überhaupt die richtige Antwort?
    for (k = 1; k < N / 2; k += 1) {
       for (j = k; j < 2 * k; j += 1) [
             x[j] = x[j-k] + x[j];//Das spielt keine große Rolle
        }
    }
}

Answer 1

Die Gesamtkomplexität beträgt tatsächlich O(N)

Behauptung: Für jedes k haben Sie k innere Schleifendurchläufe. (überzeugen Sie sich selbst, warum dies korrekt ist)

Bezeichnen Sie die Anzahl der insgesamt inneren Schleifendurchläufe mit T(N), und lassen Sie die Anzahl der äußeren Schleifen h sein.
Dies bedeutet, dass wir haben:

T(N) = 1 + 2 + 4 + ... + 2^h 
     < 2 * 2^h               (1)
     = 2^(h+1)     
     = 2^(logN + 1)          (2)
     = 2^(log(2N))   
     = 2N

---

(1) Aus Summe oder geometrische Reihe
(2) Beachten Sie, dass die Gleichung 2^(h+1) = 2^(logN + 1) ist, weil h = logN, wir haben (wie Sie gesagt haben) logN äußere Schleifendurchläufe.