Laufzeit von Algorithmus A ist mindestens O(n2) - Warum ist es sinnlos?
Warum ist die Aussage:
Die Laufzeit von Algorithmus A ist mindestens O(n2)
bedeutungslos ist ?
Die Laufzeit von Insertion-sort-Algorithmus ist höchstens O(n2)
Ist es Richtig?
Ich habe versucht, das net, aber konnte nicht eine gute Erklärung.
Habe ich noch eine Frage:
Ich weiß, dass jede lineare Funktion a⋅n+b ist O(n) und auch O(n2). Ist es auch O(n3)?
- In welchem Zusammenhang fragst du diese Frage?
- Es ist sinnlos, weil Sie nicht in irgendeiner Algorithmus A.
- Lassen Sie Algorithmus A ist insertion-sort-Algorithmus.
- Die
Big Ohnotation stellt eine Obere Schranke der Laufzeit des Algorithmus (worst-case - Szenario). Sicherlich ist es nicht sinnlos! Neben der Analyse der worst-case-Komplexität ist einfacher, in den meisten Fällen im Vergleich mit dem Durchschnitt case Analyse eines Algorithmus. Eine Plain-Englisch Erklärungen von Big O - Ich interpretierte o(n^2) "mindestens", wie einem Laufenden Zeit, das war nicht ein schlimmer Fall ist, ist das nicht eine richtige big O in diesem Zusammenhang.
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
T(n): Laufzeit von Algorithmus A. Wir nur Sorge um die Obere Grenze und untere GrenzeT(n)Die Aussage:
T(n) >= O(n^2)Obere Schranke: Weil
T(n) >= O(n^2), dann gibt es keine Informationen über Obere Schranke vonT(n)Untere Schranke: Angenommen
f(n) = O(n^2), dann die Aussage:T(n) >= f(n), aberf(n)werden konnte alles, was ist "kleiner" alsn^2Ex:constant, n,..., So gibt es keine Schlussfolgerung über die untere GrenzeT(n)zu=> Die Aussage ist sinnlos
Ein Grund dafür könnte sein, dass eine untere Schranke ohne eine Obere Schranke ist nicht sehr nützlich. "mindestens" bedeutet, dass es exponentiell im normalen Fall. Wenn Sie nicht wissen, ist die Obere Grenze, die Sie wahrscheinlich nicht verwenden können, den Algorithmus in eine Echtzeit-Anwendung, da Sie nicht wissen können, wenn das Programm beendet ist, bevor das Universum tut.
Big O-notation, wenn Sie richtig eingesetzt, zeigt eine Obere Schranke. So besagt eine untere Schranke, wie big O ist Missbrauch der notation.
Sagte, dass "bedeutungslos" ist ein starkes Wort. Es ist sicherlich nützliche Informationen, auch wenn es nicht angemessen ist. Mit ein bisschen mehr Kontext zu deiner Frage könnte man besser helfen.
O(n^2) ist eine worst-case-Szenario, was bedeutet, dass die Laufzeit von n^2 oder schneller. Wenn seine Laufzeit mindestens O(n^2), dann bedeutet das, dass der Schnellste Lauf-Zeit A ist mindestens O(n^2). Dies bedeutet, dass es könnte auch etwas langsamer als O(n^2). Diese Aussagen bedeuten, dass Ein möglicher Laufzeit.
Ja, ist es. Die big-O-notation bezeichnet eine ganze Sammlung von Funktionen. Aber wir sollten es verwenden, um zu charakterisieren, eine Funktion so genau wie möglich. Während es wahr ist, dass
f(n) = an+bistO(n^2)oder sogarO(n^3)ist es genauer, zu sagen, dassf(n) = O(n).Einer Analogie:
Die Aussage ist ein bisschen wie zu sagen: "Das Dach meines Hauses ist in einer Höhe, die mindestens dem Boden." Wahr, aber völlig sinnlose.
O-notation, in anderen Worten bedeutet:
f(x) gehört, set O(g(x)), wenn
f(x) < C * g(x), für alle C (das sind reelle Zahlen)
d.h. Ihr Algorithmus nicht wachsen mehr als eine quadratische Funktion
Es ist nicht sinnlos, es kann verwendet werden, zum Beispiel wenn Sie nicht wissen, den genauen Algorithmus, aber Sie wissen sicherlich, dass es erfordert O(n^2) Operationen.
Zum Beispiel, wenn man nicht weiß, über Sortier-algorithmen, aber versteht, dass ein array Sortieren benötigen wir mindestens zu betrachten, jedes element kann man sagen, dass "Sortieren eines Arrays ist mindestens O(n)".
Weil niemand interessiert, wie schnell es wirkt im besten Fall, im schlimmsten Fall ist wichtig. In der Regel sind die Menschen daran interessiert zu wissen, wie viel es dauern wird, im schlimmsten Fall.
Lassen
f(n)werden, die Laufzeit des Algorithmus.Dies ist immer wahr für
f(n), da läuft die Zeit immer nicht negativ. Daher, die Aussage ist redundant."Die Laufzeit von Algorithmus A ist mindestens O(n2)" ist äquivalent zu "Die Laufzeit des Algorithmus ist Ein Großes Omega(n2)", also ist es nicht sinnlos.