Warum ist die Aussage:Laufzeit von Algorithmus A ist mindestens O (n²) - Warum ist es bedeutungslos?
Die Laufzeit des Algorithmus A mindestens O (n²)
sinnlos ist?
Die Laufzeit des Algorithmus Insertionsort ist höchstens O (n²)
Ist es richtig?
Ich versuchte das Netz, konnte aber keine gute Erklärung bekommen.
Ich habe eine weitere Frage auf:
Ich weiß, dass jede lineare Funktion a⋅n + b O (n) ist und auch O (n²). Ist es auch O (n³)?
T(n): Laufzeit von Algo A.Wir kümmern uns nur um die obere Grenze und von T(n) Die Aussage untere Grenze: T(n) >= O(n^2)
Obere Grenze: Weil T(n) >= O(n^2) gibt, dann ist oberen keine Informationen über T(n) untere Grenze gebunden: f(n) = O(n^2) Angenommen, dann ist die Aussage: T(n) >= f(n), aber f(n) könnte alles sein, was „kleiner“ als n^2 ist, Ex: constant, n,..., also gibt es keine Aussage über untere Grenze von T(n) zu
=> Die Aussage ist sinnlos
+1 Dies ist die richtige Antwort. – chepner
Ein Grund könnte sein, dass eine untere Schranke ohne obere Schranke nicht sehr nützlich ist. "mindestens" bedeutet, dass es im Normalfall exponentiell sein kann. Wenn Sie die obere Grenze nicht kennen, können Sie den Algorithmus wahrscheinlich nicht in einer realen Anwendung verwenden, da Sie nicht wissen können, ob das Programm vor dem Universum beendet wird.
Die große O-Notation zeigt bei korrekter Verwendung eine obere Grenze an. Wenn man also eine Untergrenze als großes O angibt, missbraucht man die Notation.
Das sagte "bedeutungslos" ist ein starkes Wort. Es ist sicherlich nützliche Informationen, auch wenn es nicht ausreicht. Mit ein wenig mehr Kontext zu Ihrer Frage könnten Sie bessere Hilfe bekommen.
Danke für Ihre genaue Antwort. Wenn ich A als Einfügesortieralgorithmus betrachte, dann ist es nützlich zu sagen: "Die Laufzeit von Algorithmus A ist mindestens O (n2)?" In diesem Zusammenhang? – tanmoy
ein weiterer Zweifel: Jede lineare Funktion an + b ist O (n) und ist auch O (n^2). Ist es auch O (n^3)? – tanmoy
Wie gesagt, es ist korrekt und sinnvoll, die untere Grenze der Ausführungszeit anzugeben, es ist nur ungewöhnlich, dass dafür eine große O-Notation verwendet wird, die normalerweise für die obere Grenze der Zeitkomplexität reserviert ist. Die Aussage "es ist mindestens n2" wird formeller als (großes) Omega (n^2) beschrieben, was "unten asymptotisch begrenzt durch n^2" bedeutet. Du solltest also nicht "O (..)" verwenden, außer du meinst "oben begrenzt, asymptotisch". http://en.wikipedia.org/wiki/Big_O_notation –
"Die Laufzeit von Algorithmus A ist mindestens O (n2)" entspricht "Die Laufzeit von Algorithmus A ist Big Omega (n2)", also ist es nicht bedeutungslos.
O-Notation, mit anderen Worten bedeuten: f (x) gehört gesetzt O (g (x)), wenn f (x) < C * g (x) für alle C (die reellen Zahlen)
dh Ihr Algorithmus wächst nicht mehr als eine quadratische Funktion
es ist nicht bedeutungslos, es kann beispielsweise verwendet werden, wenn Sie den genauen Algorithmus nicht kennen, aber Sie wissen sicherlich, dass es O benötigen (n^2) Operationen.
Zum Beispiel, wenn man nicht über Sortieralgorithmen weiß, aber versteht, dass, um ein Array zu sortieren, wir mindestens jedes Element betrachten müssen, kann man sagen, dass "ein Array sortiert ist mindestens O (n) ".
@ downvoter: jede Erklärung? –
Da es im besten Fall niemanden interessiert, wie schnell es funktioniert, ist der Worst Case wichtig. Normalerweise sind die Leute interessiert zu wissen, wie viel es im schlimmsten Fall dauern wird.
Lassen Sie f(n) die Laufzeit des Algorithmus sein.
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
Dies ist immer wahr für f(n), da die Zeit läuft, ist immer nicht negativ. Daher ist die Aussage redundant.
O (n^2) ist ein Worst-Case-Szenario, was bedeutet, dass die Laufzeit von A n^2 oder schneller ist. Wenn die Laufzeit mindestens 0 (n^2) ist, bedeutet das, dass die kürzeste Laufzeit, die A haben kann, mindestens 0 (n^2) ist. Dies bedeutet, dass es auch etwas langsamer sein kann als O (n^2). Diese Aussagen bedeuten, dass A eine mögliche Laufzeit haben kann.
Ich weiß, dass jede lineare Funktion einer + b ist O (n) und auch O (n^2). Ist es auch O (n^3)?
Ja, ist es. Die Groß-O-Notation bezeichnet eine ganze Sammlung von Funktionen. Aber wir sollten es verwenden, um eine Funktion so genau wie möglich zu charakterisieren. Während es wahr ist, dass f(n) = an+bO(n^2) oder sogar O(n^3) ist, ist es genauer zu sagen, dass f(n) = O(n).
Eine Analogie:
Die Aussage ist ein bisschen wie wenn man sagt: „Das Dach meines Hauses auf einer Höhe ist, die zumindest der Boden ist“ Richtig, aber völlig uninformativ.
In welchem Kontext stellen Sie diese Frage? – nhahtdh
Es ist bedeutungslos, weil Sie keinen Algorithmus A zur Verfügung gestellt haben. – aqua
Lassen Sie Algorithmus A Insertion Sortierung Algorithmus. – tanmoy