Ich lerne gerade Big-O Notation und stolperte über diesen kleinen Algorithmus in einem anderen Thread:
%Vor%Laut dem Autor des Posts ist die Komplexität Θ (n), aber ich kann nicht herausfinden, wie. Ich denke, die Komplexität der while-Schleife ist Θ (log (n)). Die Komplexität der for-Schleife aus dem, was ich dachte, wäre auch Θ (log (n)), weil die Anzahl der Iterationen jedes Mal halbiert würde.
Also, wäre die Komplexität des Ganzen nicht Θ (log (n) * log (n)), oder mache ich etwas falsch?
Bearbeiten: Das Segment ist in der besten Antwort auf diese Frage: Ссылка =
Stellen Sie sich der Einfachheit halber n = 2^k vor. Wie oft wird x inkrementiert? Es folgt leicht dies ist Geometrische Serie
2 ^ k + 2 ^ (k - 1) + 2 ^ (k - 2) + ... + 1 = 2 ^ (k + 1) - 1 = 2 * n - 1
Also dieser Teil ist Θ(n) . Auch i get wird halbiert k = log n mal und es hat keine asymptotische Wirkung auf Θ(n) .
Der Wert von i für jede Iteration der while -Schleife, die auch angibt, wie viele Iterationen die for -Schleife hat, sind n, n / 2, n / 4, ... und der Gesamtwert Komplexität ist die Summe dieser. Das bedeutet ungefähr 2n, was dir dein Theta (n) bringt.