Warum wird Big O anstelle von Big Theta unterrichtet?

21

Die Big O-Notation bietet eine obere Schranke für eine Funktion, während Big Theta eine enge Schranke bietet. Ich finde jedoch, dass die Big O-Notation in der Regel (und informell) unterrichtet und verwendet wird, wenn sie wirklich Big Theta bedeutet.

zB "Quicksort ist O (N ^ 2)" kann zu der viel stärkeren Aussage "Quicksort ist Θ (N ^ 2)" werden

Obwohl die Verwendung von Big O technisch korrekt ist, wäre eine häufigere Verwendung von Big Theta nicht aussagekräftiger und würde zu weniger Verwirrung führen? Gibt es einen historischen Grund, warum dieses Big O häufiger verwendet wird?

Wikipedia- Hinweise:

Informell, insbesondere in der Informatik, darf die Big-O-Notation häufig missbraucht werden, um eine asymptotische enge Bindung zu beschreiben, bei der die Verwendung der Big-Theta-Notation in einem bestimmten Kontext sachgerechter sein könnte.

notation big-o big-theta tskuzzy
quelle
3
Ich weiß, dass dies nicht wirklich die Frage betrifft, aber Quicksort ist kein Theta (N ^ 2). Es ist O (N ^ 2).
Sternberg
Big O ist das, was Anfänger / Nicht-CS-Leute wissen müssen. Big Theta ist das, was in einer Einführung in Algorithmen behandelt wird, die nicht von jedem Major verwendet werden. Diejenigen, die eine Algorithmusklasse hatten, können auf Wunsch tiefer in die Big O-Notation einlesen. Ich bin nicht sicher, worauf sich das Wikipedia-Zitat bezieht. Mit akademischen Publikationen bekommen Sie bei einer Konferenz die Kehle durchgeschnitten, wenn Sie Big O und Big Theta verwechseln. Einige Menschen verbringen ihr ganzes Leben damit, dem Theta nachzujagen, und das sind SCHWERE SCHWERE Probleme.
Job
@jsternberg Technisch bist du richtig. Dies ist auch wahr, aber bedeutungslos: "Quicksort ist in jedem Fall (schlechteste, beste, ...) O (n ^ 100). Aber ich stimme mit OP überein, es sollte genauer sein: QuickSort ist der schlechteste Fall Theta (N ^ 2) QuickSort ist im besten Fall Theta (NlogN), da wir in jedem Fall eine andere Funktion erhalten
Eldar

Antworten:

26

Denn bei der Analyse der Performance interessiert Sie in der Regel nur der Worst-Case. Daher ist es ausreichend, die Obergrenze zu kennen.

Wenn es für eine bestimmte Eingabe schneller als erwartet ausgeführt wird, ist dies kein kritischer Punkt. Es sind meist vernachlässigbare Informationen.

Einige Algorithmen sind, wie @Peter Taylor feststellte, überhaupt nicht eng gebunden. Siehe QuickSort zum Beispiel O (n ^ 2) und Omega (n).

Außerdem sind enge Grenzen oft schwieriger zu berechnen.

Siehe auch:

Falke
quelle
6
Big O muss aber nicht unbedingt der Worst-Case-Performance entsprechen. Ich könnte sagen, Quicksort läuft in O (2 ^ n) und ist zu 100% korrekt. Es wäre viel aussagekräftiger, wenn ich sagen würde, dass der Algorithmus X in Theta (N ^ 2) und nicht in O (N ^ 2) ausgeführt wird.
tskuzzy
Außerdem werden bei der Analyse von Algorithmen fast immer enge Grenzen berechnet und nicht nur eine obere Grenze. Ich frage, warum die Leute nicht einfach die viel ausdrucksstärkere Theta-Notation verwenden, wenn sie können.
tskuzzy
9
Ich habe dir gesagt, warum die meisten Programmierer es nicht benutzen. Wir sind faul und brauchen nicht so viel Genauigkeit. Niemand hält Sie davon ab, Big Theta zu verwenden, wenn Sie möchten. Mach schon, mach schon. Ihre Algorithmus-Wahl wird höchstwahrscheinlich nicht so viel davon profitieren. Ich habe noch nie von einem Programmierer gehört, der durch die große O-Notation verwirrt ist. Auch ich finde es überhaupt nicht verwirrend.
Falcon
9

Ein Grund ist, dass es viele Fälle gibt, in denen Θ einfach nicht bekannt ist. Zum Beispiel ist die Matrixmultiplikation O (n ^ 2.376), es ist jedoch keine enge Bindung bekannt. Sicher, soweit ich das beurteilen kann, gibt es eine enge Grenze für die Matrixmultiplikation, aber wir kennen ihren Wert nicht.

MSalters
quelle
Dies wäre jedoch die Grenze für die Laufzeit eines Problems, nicht eines bestimmten Algorithmus. Während die Matrixmultiplikation im Allgemeinen schneller als die kubische Zeit gelöst werden kann, ist der naive Algorithmus Θ (n ^ 3), egal was passiert.
tskuzzy
5
@tskuzzy, nimm quicksort. Es hat keine Theta-Grenze, weil es O (n ^ 2) und Omega (n) ist.
Peter Taylor