Anzahl der Aufrufe von Schleifen bestimmen

[lennero]

Hallo.
Die Aufgabe lautet:
Give the order of growth (as a function of N ) of the running time of the following code fragment:

int N = a.length; //length of an array
int sum = 0;
for(int n = N, i > 0; n /= 2)
    for(int j = 0; j < n; j++)
        sum++;

Bevor ich meinen Versuch aufdrösel, wollte ich mal fragen, ob man solche Aufgaben auf Anhieb ohne auch nur einen Stift anzufassen im Kopf lösen sollte (mit Erfahrung)?

Zeile 1, 2 und 3 werden genau 1 mal aufgerufen.
Zeile 4 wird log2(N) + 1 mal aufgerufen.

Für ein N = 8 wird die 5. Zeile genau N mal durchlaufen. Danach wird n halbiert. Anschließend wird Zeile 5 genau N/2 mal durchlaufen. Danach N/4 mal und zum Schluss 1 mal. Das ganze genau log2(N) mal.

Am Ende habe ich dann für Zeile 5 raus: N + N/2 + N/4 + 1

Das scheint auch richtig zu sein, nur ist das ja viel zu spezifisch. Wie kann ich das für alle N berechnen? Der obere Term gilt ja nur für N = 8. Für größere N würden einfach mehr N/x Terme auftauchen.

Wie kann ich die Summe (1/2 + 1/4 + 1/8 ... 1/(log2(N) + 1)) verallgemeinern? Kann ich hier die allgemeine Summenformel verwenden?

 

[fhoffmann]

Bei solchen Fragen kann man auch "ungenau" rechnen, also N + N/2 + N/4 + N/8 + ... = 2*N
Interesant ist nur die Größenordnung.