Big-Oh-Notation für eine einzelne while-Schleife, die zwei Hälften eines Arrays mit zwei Iterator-Vars abdeckt

Versuch, mein Big-O-Verständnis für einen Test aufzupeppen (Ein sehr grundlegendes Verständnis ist offensichtlich erforderlich) und machte einige Übungsprobleme in meinem Buch.Big-Oh-Notation für eine einzelne while-Schleife, die zwei Hälften eines Arrays mit zwei Iterator-Vars abdeckt

Sie gaben mir die folgenden Ausschnitt

public static void swap(int[] a) 
{ 
    int i = 0; 
    int j = a.length-1; 

    while (i < j) 
    { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
     i++; 
     j--; 
    } 
}

Ziemlich einfach denken, ich verstehe. 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 O (n/2) + O (n/2) = O (2n/2) = O (n)

Jetzt bitte vergeben, 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 mir jemand diese Frage klären?

Dank

Quelle

2015-09-07 Habitat

FYI: Auch wenn Sie nur über ein halbes Array iterieren - etwas wie 'sumOddIndexElements()', zum Beispiel - es ist immer noch O (n). Der konstante Faktor von 1/2 geht weg. Wenn Sie mit der Analyse komplexerer Algorithmen beginnen, ist es hilfreich, zu Beginn der Analyse von exakten Zählwerten zu großen O-Werten zu wechseln. Dann werden Ihre Zwischenschritte einfacher, weil Sie Begriffe wegwerfen können. I.E. Wenn ein Unterprogramm O (n) + O (log n) funktioniert, können Sie es für den Rest der Analyse sofort auf O (n) reduzieren. – japreiss

@japreiss Es tut mir leid, ich versuche nicht, überflüssig zu sein, aber dein letzter Satz verwirrte mich ein wenig. Wenn ich richtig verstehe, wird O (log n) zu einem bestimmten Punkt unbedeutend genug für O (n), dass es sich nicht lohnt, in die Zeiteffizienz zu rechnen, und deshalb lassen wir es fallen. – Habitat

Durch die Definition von großen O, wenn Sie Begriffe hinzufügen, können Sie immer alles außer dem asymptotisch größten fallen lassen. Sie können beweisen, dass "n + log n <2n" aber "2n" ist O (n). Also ja, es ist unbedeutend, auf eine sehr gut definierte Art und Weise. – japreiss

Die Tatsache, dass es eine Schleife hat, ist mir denken, was es ist O (n) sowieso.

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 braucht, 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) kommen.

Es wird anders, wenn die Größe der Schleife als ein konstanter Faktor andere geändert wird, sondern als logarithmische Funktion oder eine Exponentialfunktion n, zum Beispiel, wenn eine Größe ist 100 und Schleife ist 2, Größe 1000 ist und Schleife ist 3, Größe ist 10000 und Schleife 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 immer 100 mal wiederholen würden, würde Ihr Algorithmus unabhängig von der Schleifengröße O(1) sein (d. H. In einer konstanten Zeit arbeiten).

ich auch, wenn die Gleichung ich war zu bekommen kam fragen, wurde es irgendwo im Baseballstadion von korrekt.

Ja. Wenn Ihre Gleichung schließlich eine Form von n * C + Y ist, wobei C eine Konstante ist und Y ein anderer Wert ist, ist das Ergebnis O(n), unabhängig davon, ob see größer als 1 oder kleiner als 1 ist.

Quelle

2015-09-07 06:02:34 Abel

Danke für Ihre Antwort. Ich habe mich auch gefragt, ob die Gleichung, die ich mir ausgedacht hatte, irgendwo im Spiel war, richtig zu sein. Es hilft, darüber mathematisch nachzudenken, aber ich mache damit eine Aufnahme im Dunkeln. Eine Validierung zu diesem speziellen Aspekt wäre großartig. Ich nehme an, es ist entweder "O (n/2) + O (n/2) oder nur O (n/2) und dann ignoriere ich/2 alltogether" – Habitat

@Habitat: Ich habe die Antwort aktualisiert, um das zu beantworten;) . – Abel

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 ist es O (n).

Nehmen wir an, Sie laufen 2 separate Schleifen. 2 + 6 * (n/2) + 6 * (n/2). In diesem Fall wird es wieder O (n) sein.

Aber wenn wir eine verschachtelte Schleife ausführen. 2+ 6 * (n * n). Dann wird es sein O (n^2)

Entfernen Sie immer die Konstanten und machen Sie die Mathematik. Du hast die Idee.

Quelle

2015-09-07 06:07:13 Sorter

Also lass mich das wirklich schnell kaputt machen. Es sind 2 Anfangsoperationen + 6 Operationen für jede Iteration mal die gesamten Iterationen? – Habitat

Ja! Du hast Recht. – Sorter

Ihr Beispiel mit 'O (2n)' endet immer noch als 'O (n) ', weil es immer noch einzeln abhängig von der Größe ist. Andernfalls, wenn zwei Schleifen mit einem anderen Ergebnis ergeben, sollte eine halbe Schleife auch ein anderes Ergebnis in der Groß-O-Notation ergeben. – Abel

Da j-i um 2 Einheiten bei jeder Iteration abnimmt, werden N/2 von ihnen genommen (unter der Annahme N=length(a)).

Daher ist die Laufzeit in der Tat O(N/2). Und O(N/2) entspricht genau O(N).

Quelle

2015-09-07 09:04:16

Big-Oh-Notation für eine einzelne while-Schleife, die zwei Hälften eines Arrays mit zwei Iterator-Vars abdeckt

Antwort

Verwandte Themen