Big O für den worst-case-Laufzeit und Ω ist für den best-case, aber warum ist Ω verwendet, die im schlimmsten Fall auch manchmal?
Ich bin verwirrt, ich dachte, dass Sie mit Großen O für den worst-case-Laufzeit und Ω ist für den best-case? Kann mir bitte jemand erklären?
Und nicht (lg n) die best-case? und (nlg n) ist die worst-case? Oder bin ich Missverständnis, was?
Zeigen, dass die worst-case-Laufzeit von Max-Heapify auf einem heap der Größe
n ist Ω(lg n). ( Tipp: Für einen heap mit n Knoten, Knoten geben die Werte, die
Ursache Max-Heapify aufgerufen werden rekursiv an jedem Knoten auf einem Pfad
von der Wurzel nach unten auf ein Blatt.)
Edit: Nein das ist keine Hausaufgabe. im üben und diese hat eine Antwort key kaufen im confused.
http://www-scf.usc.edu/~csci303/cs303hw4solutions.pdf Problem 4(6.2 - 6)
Edit 2: So ich falsch verstanden, die Frage nicht über die Big-O-und Ω?
Analyse am Schlimmsten war der Fall : Theta(logn + k)" in Ihrem link erwähnt wurde durch den Fragesteller. ist es nicht Thetha(logn), da kann man drop + k ?
Ja, finden die anderen k-1 in der Nähe Titel wäre vernachlässigbar.
Ω(1) ist noch das beste 😉
InformationsquelleAutor Jan Tristan Milan | 2013-03-14
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist es wichtig, zu unterscheiden zwischen dem Gehäuse und dem gebunden.
Beste, Durchschnittliche und schlechteste sind Häufig Fällen von Interesse bei der Analyse von algorithmen.
Obere (O, o) und unteren (Omega, omega), zusammen mit Theta, sind gemeinsame Grenzen auf Funktionen.
Wenn wir sagen "Algorithmus X ist die worst-case Zeitkomplexität ist O(n)", wir sagen, dass die Funktion, die den Algorithmus stellt X die Leistung zu, wenn wir uns einschränken Eingänge zu worst-case-Eingaben, ist asymptotisch begrenzt von oben durch einige lineare Funktion. Sie könnte sprechen, der eine untere Schranke für die worst-case-Eingaben; oder eine Obere oder untere Schranke für die Durchschnittliche, oder besten Fall Verhalten.
Fall != Gebunden. Das heißt, "oben auf dem schlimmsten" und "untere" auf die besten" sind ziemlich vernünftige Arten von Metriken... Sie absolute Schranken für die Leistungsfähigkeit eines Algorithmus. Es bedeutet nicht, wir können nicht reden über andere Metriken.
Bearbeiten zu reagieren, um Ihre aktualisierte Frage:
Die Frage, fragt Sie, um zu zeigen, dass Omega(lg n) ist ein untere Schranke auf die schlimmsten Fall Verhalten. In anderen Worten, wenn dieser Algorithmus nicht so viel Arbeit wie Sie tun können, für eine Klasse von Eingaben, die Menge an Arbeit, die es tut, wächst mindestens so schnell wie (lg n), asymptotisch. So werden Ihre Schritte sind die folgenden: (1) geben Sie die worst-case für den Algorithmus; (2) finden Sie eine untere Schranke für die Laufzeit des Algorithmus auf Eingaben gehören zu den worst-case.
Hier ist eine illustration der Art und Weise sich dies für die lineare Suche:
Im schlimmsten Fall der linearen Suche, das Ziel-Element ist nicht in der Liste und alle Elemente der Liste geprüft werden müssen, um dies zu bestimmen. Also, eine untere Schranke für die worst-case Komplexität dieses Algorithmus ist O(n).
Wichtig zu beachten: für viele algorithmen, die Komplexität in den meisten Fällen wird begrenzt von oben und unten durch einen gemeinsamen Satz von Funktionen. Es ist sehr üblich, für die Theta-gebunden gelten. So könnte es sehr gut der Fall sein, dass Sie nicht bekommen eine andere Antwort für Omega, als Sie für O, in jedem Fall.
Ich würde eher sagen, dass das vernünftig gebunden ist, ist die Obere Schranke für den schlimmsten Fall, und dass Quicksort ist die Ausnahme (in der, die wir lieber ignorieren die pathologischen schlimmsten Fall, um zu rechtfertigen, mit es über einen wahren O(n log n) worst-case-Algorithmus). Das heißt, ich habe keine Referenzen oder Anmeldeinformationen, um wieder den Anspruch, die "Obere Schranke für worst-case" ist "sinnvoller" als die "Obergrenze des durchschnittlichen Fall", so kann ich klären, dass dies meine Einschätzung, nicht allgemein akzeptiert.
In jedem Programm, sind Sie ständig worst-case-Eingaben? In der Regel nicht, so average-case-Komplexität ist, was bestimmt Ihre tatsächliche Performanz, für jeden Algorithmus, pathologische oder nicht. Jedoch, eine logische Folge von diesem ist, dass die algorithmen mit einer pathologischen worst-case-Komplexität führen kann, um DOS-exploits, wie mit der letzten-ish Java
parseDouble()Fehler. Ein weiterer wäre, dass es Sinn macht entsprechenden algorithmen für das Sortieren von input-Daten, die Sie haben, das ist der Grund, warum timsort ist genial.Im Allgemeinen würde ich Zustimmen, dass die Metrik, auf welche Grundlagen die Wahl des Algorithmus hängt von den Umständen ab. Zum Beispiel, einige Situationen nennen könnte, für einen Algorithmus mit guter average-case-performance und tolerieren gelegentliche schlechte Leistung, während andere nennen könnte, für mehr durchgängig skalierbare Leistung. In theoretischen Kontexten, Ober - /worst-und untere/besten sind wichtiger, weil Sie Dinge sagen, darüber, wo die Probleme wohnen in der Komplexität der Klassen.
"Also, eine untere Schranke für die worst-case Komplexität dieses Algorithmus ist O(n)." ein Tippfehler? Sollte es nicht sein: "Also, eine untere Schranke für die worst-case Komplexität dieses Algorithmus ist Omega(n)?".
InformationsquelleAutor Patrick87
Tatsächlich, Sie mit Großen O für eine Funktion, die schneller wächst als Ihr worst-case-Komplexität, und Ω eine Funktion, die wächst langsamer als Ihre worst-case-Komplexität.
Also hier sind Sie gefragt, um zu beweisen, dass Ihre worst-case-Komplexität ist schlimmer als lg(n).
lg(n)" - vielleicht sollte man sagen "ist (asymptotische) größer als".Also habe ich falsch verstanden, die Frage nicht über die Big-O-und Ω?
in unserer Prüfung, die Sie haben, zu sagen, "schlimmer" verursachen, wenn seine größer es ist schlimmer, richtig?
InformationsquelleAutor Axelle Ziegler
O ist die Obere Grenze (ich.e, worst case)
Ω ist die untere Grenze (d.h., im besten Fall)
Dem Beispiel ist zu sagen, dass im schlimmsten Eingang für max-heapify ( ich denke die schlimmsten Eingang reverse-bestellt-Eingang) die Laufzeit muss die Komplexität (zumindest) lg n . Daher Ω (lg n), da Sie die untere Grenze für die Ausführung von Komplexität.
InformationsquelleAutor fabiim