Ich versuche, mein Big-O-Verständnis für einen Test aufzufrischen (Ein sehr grundlegendes Verständnis von Big-O ist offensichtlich erforderlich). Ich komme auf und mache einige Übungsprobleme in meinem Buch.
Sie gaben mir den folgenden Ausschnitt
%Vor%Ziemlich einfach zu verstehen, denke ich. Es hat zwei Iteratoren, die jeweils die Hälfte des Arrays mit einem festen Betrag an Arbeit abdecken (was ich denke, taktet sie beide bei O (n / 2))
Daher gilt O (n / 2) + O (n / 2) = O (2n / 2) = O (n)
Nun bitte verzeihen Sie, da dies mein derzeitiges Verständnis ist und das war mein Versuch, das Problem zu lösen. Ich habe viele Beispiele für Big-O-Online gefunden, aber keine, die so ähnlich sind, wobei die Iteratoren das Array im Wesentlichen zur gleichen Zeit erhöhen und modifizieren.
Die Tatsache, dass es eine Schleife hat, lässt mich denken, dass es sowieso O (n) ist.
Würde irgendjemand etwas dagegen haben, das für mich zu klären?
Danke
Die Tatsache, dass es eine Schleife hat, lässt mich denken, dass es sowieso O (n) ist.
Das ist richtig. Nicht weil es eine Schleife macht, sondern weil es eine Schleife ist, die von der Größe der Matrix um einen konstanten Faktor abhängt: Die Groß-O-Notation ignoriert jeden konstanten Faktor. O(n) bedeutet, dass der einzige Einfluss auf den Algorithmus auf der Größe des Arrays basiert. Dass es tatsächlich die Hälfte dieser Zeit dauert, spielt keine Rolle für Groß-O.
Mit anderen Worten: Wenn Ihr Algorithmus Zeit braucht n+X , Xn , Xn + Y werden alle auf big-O O(n) herunterkommen.
Es wird anders, wenn die Größe der Schleife anders als ein konstanter Faktor geändert wird, aber als eine logarithmische oder exponentielle Funktion von n , beispielsweise wenn die Größe 100 ist und die Schleife 2 ist, ist die Größe 1000 und loop ist 3 , Größe ist 10000 und loop ist 4 . In diesem Fall wäre es beispielsweise O(log(n)) .
Es wäre auch anders, wenn die Schleife unabhängig von der Größe ist. Das heißt, wenn Sie 100 mal unabhängig von der Schleifengröße immer wiederholen würden, wäre Ihr Algorithmus O(1) (d. H. Sie arbeiten in einer konstanten Zeit).
Ich habe mich auch gefragt, ob die Gleichung, die ich mir ausgedacht habe, irgendwo im Spiel war, dass sie korrekt ist.
Ja. Wenn Ihre Gleichung schließlich eine Form von n * C + Y ist, wobei C eine Konstante und Y ein anderer Wert ist, lautet das Ergebnis O(n) , unabhängig davon, ob see größer als 1 ist. oder kleiner als 1 .
Sie haben Recht mit der Schleife. Loop bestimmt das Big O. Aber die Schleife läuft nur für die Hälfte des Arrays.
So ist es. 2 + 6 * (n / 2)
Wenn wir n sehr groß machen, sind andere Zahlen wirklich klein. Sie werden also keine Rolle spielen. Also sein O (n).
Nehmen wir an, Sie haben zwei separate Schleifen. 2 + 6 * (n / 2) + 6 * (n / 2) . In diesem Fall ist es wieder O (n).
Aber wenn wir eine verschachtelte Schleife ausführen. 2+ 6 * (n * n) . Dann wird es O (n ^ 2)
seinEntferne immer die Konstanten und mach die Mathematik. Du hast die Idee.
As j-i verringert sich um 2 units bei jeder Iteration, N/2 von ihnen werden genommen (angenommen N=length(a) ).
Daher ist die Laufzeit tatsächlich O(N/2) . Und O(N/2) entspricht genau O(N) .