Kämpfen mit dem Unterschied zwischen O, Ω und Θ?

Question

Ich beschäftige mich derzeit mit Daten über Datenstrukturen und Algorithmen. Ich habe eine Abschlussprüfung gemacht und weiß, dass es bei verschiedenen Sortier- und Suchalgorithmen Fragen hinsichtlich der Zeitkomplexität im ungünstigsten Fall geben wird.

Ich glaube, ich verstehe die allgemeine Idee von O, Ω und Θ. O steht für die obere Grenze, Ω für die obere und untere Grenze und Θ für die untere Grenze.

Also, wenn wir Frage (b) aus dem Beispiel unten betrachten, bin ich verwirrt, ob meine Antwort O (n log n) oder Θ (n log n) sein sollte?

Ursprünglich dachte ich, Θ ​​sei ausschließlich für die Zeitkomplexität im ungünstigsten Fall gedacht, aber ich sehe, dass sich die Leute auf die Komplexität der Worst-Case-Zeit mit O beziehen.

Answer 1

Okay, haben Sie einige rückwärts, so O-Notation bezeichnet den schlimmsten Fall und ist ein Oberegrenze.

Big Theta bezeichnet eine enge asymptotische Bindung. Dies bedeutet, dass der schlechteste und der beste Fall dieselbe Funktion haben. Im Wesentlichen verwenden wir Big Theta, wenn Big O und Big Omega uns die gleichen Grenzen geben.

Große Omega bezeichnet den besten Fall, eine untere Grenze.

Verwenden Sie im Allgemeinen Big O für den schlimmsten Fall und verwenden Sie große Theta, wenn der schlechteste und der beste Fall identisch sind. Wenn Sie nur Big O und Big Omega verwenden, sind Sie vollkommen objektiv korrekt