•  21-08-2019
  •  | 
  •  

Frage

. HINWEIS: Ich bin ultra-Neuling auf Algorithmus Analyse also nicht jede meiner Affirmationen als absolute Wahrheiten nehmen, etwas (oder alles), die ich könnte falsch angeben

Hallo, ich lese über Algorithmus Analyse und „Big-O-Notation“ und ich fiel verwirrt über etwas.

Nehmen wir an, dass Sie alle Permutationen einer char-Array zu drucken, werden gebeten, für [a, b, c] würden sie ab, ac, ba, bc, ca und cb sein.

Nun ja, eine Möglichkeit, es zu tun wäre (in Java): 

for(int i = 0; i < arr.length; i++)
    for(int q = 0; q < arr.length; q++)
        if(i != q)
            System.out.println(arr[i] + " " + arr[q]);

Dieser Algorithmus hat eine Notation von O (n 2 ) , wenn ich richtig.

Ich dachte, andere Art und Weise, es zu tun: 

for(int i = 0; i < arr.length; i++)
    for(int q = i+1; q < arr.length; q++)
    {
        System.out.println(arr[i] + " " + arr[q]);
        System.out.println(arr[q] + " " + arr[i]);
    }

Nun dieser Algorithmus ist doppelt so schnell als der ursprüngliche , aber wenn ich falsch liege, für Big-O-Notation ist es auch ein O ( 2 )

Ist das richtig? Wahrscheinlich ist es nicht so werde ich anders formulieren: Wo bin ich falsch ??

War es hilfreich?

Lösung

Sie sind richtig. O-Notation gibt Ihnen eine Vorstellung davon, wie die Algorithmus Skalen, nicht die absoluten Geschwindigkeit. Wenn Sie mehr Möglichkeiten hinzufügen, werden beide Lösungen die gleiche Art und Weise skalieren, aber man wird immer doppelt so schnell wie der andere sein.

O (n) Operationen können ebenfalls langsamer als O (n ^ 2) Operationen für hinreichend kleinen 'n'. Stellen Sie sich Ihre O (n) Berechnung beinhaltet 5 Quadratwurzeln nehmen, und Ihr O (n ^ 2) Lösung ist ein einziger Vergleich. Die O (n ^ 2) Betrieb wird schneller sein für kleine Datenmengen. Aber wenn n = 1000, und Sie tun 5000 Quadratwurzeln aber 1000000 Vergleiche, dann die O (n) beginnen könnte besser aussehen.

Andere Tipps

Ich denke, die meisten Menschen sind sich einig erste ist O (n ^ 2). Äußere Schleife läuft n-mal und des inneren Schleife läuft n-mal alle Zeit äußere Schleife läuft. So ist die Laufzeit ist O (n * n), O (n ^ 2).

Das zweite ist O (n ^ 2), da die äußere Schleife läuft n mal. Die inneren Schleifen laufen n-1 mal. Im Durchschnitt für diesen Algorithmus läuft innere Schleife n / 2-mal für jede äußere Schleife. so dass die Laufzeit dieses Algorithmus ist O (n * n / 2) => O (1/2 * n ^ 2) => O (n ^ 2).

Big-O-Notation sagt nichts über die Geschwindigkeit des Algorithmus mit Ausnahme, wie schnell es sich relativ ist, wenn die Größe der Eingabe ändert.

Ein Algorithmus könnte sein, O (1) noch eine Million Jahre dauern. Ein anderer Algorithmus kann O (n ^ 2), aber schneller als ein O (n) Algorithmus für kleine n.

Einige der Antworten href="https://stackoverflow.com/questions/941283/when-does-big-o-notation-fail"> diese Frage Frage auch hilfreich sein kann.

Das Ignorieren des Problems des Programms Ausgang "Permutation" Aufruf:

Big-O-Notation läßt konstante Koeffizienten. Und 2 ist ein konstanter Koeffizient.

Also, es ist nichts falsch für Programme zweimal schneller als das Original gleich O hat ()

Sie sind richtig. Zwei Algorithmen sind äquivalent in O-Notation, wenn einer von ihnen eine konstante Menge an Zeit in Anspruch nimmt mehr ( „A dauert 5 Minuten mehr als B“), oder ein Vielfaches ( „A dauert 5-mal länger als B“) oder von beiden ( "A dauert 2 mal B plus eine zusätzliche 30 Millisekunden ") für alle Größen des Eingangs.

Hier ist ein Beispiel, das einen grundsätzlich anderen Algorithmus verwendet eine ähnliche Art von Problem zu tun. Zunächst wird die langsamere Version, die ähnlich wie Ihr ursprüngliches Beispiel aussieht: 

boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
    for (int j = i; j < arr2.length(); j++) {
        if (arr1[i] == arr2[j]) {
            arraysHaveAMatch = true;
        }
    }
}

Das hat O (n ^ 2) Verhalten, genau wie Ihr Original (es verwendet auch die gleiche Abkürzung Sie den j-Index aus dem i-Index entdeckt zu starten statt von 0) gewonnen. Hier ist ein anderer Ansatz: 

boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
    set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
    if (set.contains(arr2[j])) {
        arraysHaveAMatch = true;
    }
}

Nun, wenn Sie diese versuchen ausführen, werden Sie wahrscheinlich feststellen, dass die erste Version schneller läuft. Zumindest wenn man mit Arrays der Länge 10 versuchen Da die zweite Version hat mit der Erstellung der HashSet Objekt und alle seine internen Datenstrukturen zu befassen, und weil es einen Hash-Code für jede ganze Zahl zu berechnen. Allerdings, wenn Sie es mit Arrays der Länge 10.000.000 versuchen werden Sie eine ganz andere Geschichte finden. Die erste Version hat etwa 50.000.000.000.000 Zahlenpaare zu untersuchen (etwa (N * N) / 2); Die zweite Variante hat Hashfunktion Berechnungen auf etwa 20.000.000 Nummern (etwa 2 * N) durchzuführen. In diesem Fall möchten Sie sicher die zweite Version !!

Die Grundidee hinter Big O-Berechnungen (1) ist es recht einfach zu berechnen (Sie müssen nicht über Details kümmern, wie, wie schnell Ihr CPU ist oder welche Art von L2-Cache hat), und (2) die kümmert sich um die kleinen Probleme ... sie sind schnell genug, um trotzdem: es die großen Probleme ist, die dich töten! Diese sind nicht immer der Fall ist (manchmal ist es nicht egal, welche Art von Cache Sie haben, und manchmal ist es ganz gleich, wie gut die Dinge auf kleine Datenmengen durchführen), aber sie sind nahe genug, um wahr oft genug für Big O nützlich zu sein.

Sie haben Recht über sie beide sind Big-O n quadriert, und Sie bewiesen, dass tatsächlich in Ihrer Frage um wahr zu sein, wenn Sie „, sagte nun dieser Algorithmus ist zweimal , so schnell als das Original. " Doppelt so schnell Mittel mit 1/2 multipliziert, die eine Konstante ist, so definitions sie in dem gleichen Satz Big-OS ist.

Eine Möglichkeit, über Big O des Denkens ist zu prüfen, wie gut die verschiedenen Algorithmen auch in wirklich unfair Umstände ergehen würde. wenn man auf einem wirklich leistungsfähigen Supercomputer ausgeführt wurde und die andere auf einer Armbanduhr zum Beispiel ausgeführt wurden. Wenn es möglich ist, ein N zu wählen, die so groß ist, dass, obwohl der schlechte Algorithmus auf einem Supercomputer läuft, noch die Armbanduhr zuerst beenden kann, dann haben sie unterschiedliche Big O Komplexität. Wenn auf der anderen Seite können Sie sehen, dass der Supercomputer wird immer gewinnen, unabhängig davon, welcher Algorithmus wählten Sie oder wie groß Ihre N war, dann beide Algorithmen müssen per Definition die gleiche Komplexität.

Ihren Algorithmen, war der schnelle Algorithmus nur doppelt so schnell wie die ersten. Das ist nicht genug, um einen Vorteil für die Armbanduhr der Supercomputer zu schlagen, selbst wenn N war sehr hoch, 1 Million, 1trillion oder sogar Grahams Zahl könnte die Taschenuhr nie den Supercomputer schlägt mit diesem Algorithmus. Das gleiche würde gelten, wenn sie Algorithmen getauscht. Daher beiden Algorithmen, durch Definition von Big O, die gleiche Komplexität.

Angenommen, ich einen Algorithmus hatte die gleiche Sache in O ( n ) Zeit zu tun. Nehmen wir nun an auch ich habe Ihnen eine Reihe von 10000 Zeichen. Ihre Algorithmen würden n ^ 2 und (1/2) n ^ 2 Zeit, die 100 Millionen und 50 Millionen ist. Mein Algorithmus würde 10.000 nehmen. Klar, dass Faktor 1/2 ist ein Unterschied nicht machen, da mein so viel schneller ist. Die n ^ 2 Begriff soll dominate die wenige Begriffe wie n und 1/2, wodurch sie im wesentlichen vernachlässigbar.

Das Big-O-Notation eine Familie von Funktion ausdrücken, so sagen "dieses Ding ist O (n²)" bedeutet nichts

Das ist nicht Pedanterie, es ist der einzige, richtige Weg, um diese Dinge zu verstehen.

O (f) = {g | existiert x_0 und c, so dass für alle x> x_0, g (x) <= f (x) * c}

Angenommen nun, dass Sie die Schritte sind zu zählen, die Ihr Algorithmus, im schlimmsten Fall , hat in der Bezeichnung der Größe der Eingabe: Aufruf diese Funktion f. Wenn f \ in O (n²), dann kann man sagen, dass Ihr Algorithmus eine Worst-Case-O (n²) (aber auch O (n³) oder O (2 ^ n)). Die Sinnlosigkeit der Konstanten aus der Definition folgen (siehe dass c?).

Der beste Weg, Big-O-Notation zu verstehen, ist das mathematische Verständnis für die Idee, die hinter der Notation zu erhalten. Geben Sie für lexikalische Bedeutung des Wortes „Asymptote“ 

A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.

Dies definiert die maximale Ausführungszeit (imaginäre weil Asymptote Linie die Kurve im Unendlichen erfüllt), so etwas immer Sie unter dieser Zeit wird tun.
Mit dieser Idee, möchten Sie vielleicht wissen, Big-O, Klein-O und Omega-Notation.

Immer im Auge behalten, stellt Big O-Notation den "worst case" -Szenario. In Ihrem Beispiel weist der erste Algorithmus eine durchschnittliche bei Voll äußeren Schleife * vollständiger inneren Schleife, so ist es n ^ 2 natürlich. Da der zweite Fall eine Instanz hat, wo es fast vollständige äußere Schleife * vollständige innere Schleife ist, hat es in den gleichen Stapel von n ^ 2 in einen Topf geworfen werden, da die den schlimmsten Fall ist. Von dort wird es nur besser, und der Durchschnittswert der im Vergleich zu der ersten Funktion ist viel geringer. Unabhängig davon, wie n wächst, wächst Ihre Funktionen Zeit exponentiell, und das ist alles, Big O sagt Ihnen wirklich. Die exponentiellen Kurven können stark variieren, aber am Ende des Tages, sie sind alle vom gleichen Typ.

Nicht verbunden mit StackOverflow
scroll top