Order Of Growth kompliziert für Schleifen
Was ist für das folgende Codefragment die Reihenfolge des Wachstums in Bezug auf N?
int sum = 0;
for (int i = 1; i <= N; i = i*2)
for (int j = 1; j <= N; j = j*2)
for (int k = 1; k <= i; k++)
sum++;
Ich habe mir gedacht, dass es einen lgN-Begriff gibt, aber ich bin bei der Bewertung dieses Teils festgefahren: lgN (1 + 4 + 8 + 16 + ....). Was wird der letzte Term der Sequenz sein? Ich benötige das letzte Glied, um die Summe zu berechnen.