Algorithmus Komplexität und große O-Notation

Ich nehme eine Online-Klasse über Algorithmen und ich hatte das folgende Quiz. Ich habe es falsch verstanden und versuche den Grund für die Antwort zu verstehen.Algorithmus Komplexität und große O-Notation

Welcher der folgenden Punkte ist O (n^3)?

a) 11n + 151 + 100 gn
b) 1/3 n^2
c) 25000 n^3
d) Alle der oben genannten.

Die richtige Antwort ist (d) alle oben genannten. Der Grund ist, dass die Big-O-Notation nur die obere Grenze für die Wachstumsrate der Funktion liefert, wenn n groß wird.

Ich bin mir nicht sicher, warum die Antwort nicht (c) ist. Zum Beispiel ist die obere Grenze von (b) kleiner als n^3.

Quelle

2017-04-30 Luca

Wenn etwas O (n^2), dann ist es auch O (n^3). – Lee

Obere Grenze bedeutet nicht notwendigerweise die * strengste * Grenze. – SomeWittyUsername

Es gibt keine "obere Grenze". Es gibt viele obere Grenzen. Die Big-O-Notation spezifiziert ** eine ** obere Grenze. Eine verwandte Notation liefert * die kleinste * obere Grenze, aber es ist nicht die Big-O-Notation. –

Der Grund dafür ist, dass formal, Big-O-Notation eine asymptotisches obere Schranke ist.

Also 1/3*n^2 ist O(n^2), aber es ist auch O(n^3) und auch O(2^n).

Während in der täglichen Umsetzung über Komplexität O(...) als eng (obere und untere Grenze) verwendet wird, ist die Theta-Notation oder Θ(...) der technisch korrekte Begriff dafür. siehe

Für weitere Informationen What is the difference between Θ(n) and O(n)?

Quelle

2017-04-30 17:52:51

Algorithmus Komplexität und große O-Notation

Antwort

Verwandte Themen