Zwei verschachtelte Schleifen, aber nicht quadratisch?

AP2 vorbereiten · 1 Antworten

STARTBEITRAG

#1

Zwei Schleifen, also O(n²). Das wäre mein spontaner, wahrscheinlich falscher Reflex hier:

text
for i = 1 to n:
    j = 1
    while j < n:
        j = j * 2

n ist positiv, Überläufe sollen wir ignorieren. j springt doch 1, 2, 4, 8 ... statt jeden Wert mitzunehmen. Wie schreib ich den Gedanken sauber auf?

0

Antworten

1
Antwort auf das Thema
#2

Nach k inneren Schritten ist j = 2^k. Bis n sind das ungefähr log₂(n) Schritte. Und weil du j bei jedem äußeren Durchlauf wieder auf 1 setzt, kommt das n-mal vor: Θ(n log n) für große n. Die Einrückung allein verrät die Laufzeit also noch nicht.

0