Was ist eine asymptotisch enge Obergrenze?

Aus dem, was ich gelernt habe, bedeutet asymptotisch eng gebunden, dass es von oben und unten wie in Theta-Notation gebunden ist. Aber was bedeutet eine asymptotisch enge Obergrenze für die Big-O-Notation?

Zu sagen, dass eine Big-O-Schranke "asymptotisch eng" ist, bedeutet im Grunde, dass der Autor hätte schreiben müssen . Zum Beispiel bedeutet O ( x 2 ) , dass es nicht mehr als einige konstante Zeiten  x 2 für alle x ist , die groß genug sind  ; "asymptotisch dicht" bedeutet, dass es tatsächlich einige konstante Zeiten  x 2 für groß genug  x und nicht etwa einige konstante Zeiten  x 1,999 sind .$\Theta(-)$$O(x^2)$$x^2$$x$$x^2$$x$$x^{1.999}$

Hier ist ein Beispiel, das es erklärt (und ein konkretes Beispiel für Davids gute Antwort).

$A$$O(n^3)$$n$$A$$O(n)$$\Omega(n)$$\Theta(n)$