Anzahl der Aufrufe von Schleifen bestimmen

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

Java:
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?
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben