Co to jest asymptotycznie ciasna górna granica?

Z tego, czego się nauczyłem, asymptotycznie ścisłe wiązanie oznacza, że ​​jest ono wiązane od góry i od dołu jak w notacji theta. Ale co oznacza asymptotycznie ciasna górna granica dla notacji Big-O?

Powiedzenie, że granica wielkiej litery O jest „asymptotycznie ciasna” oznacza w zasadzie, że autor powinien napisać . Na przykład O ( x 2 ) oznacza, że ​​jest to nie więcej niż kilka stałych czasów  x 2 dla wszystkich wystarczająco dużych  x ; „asymptotycznie ciasny” oznacza, że ​​tak naprawdę są to stałe czasy  x 2 dla wystarczająco dużego  x, a nie, powiedzmy, pewne stałe czasy  x 1,999 .$\Theta(-)$$O(x^2)$$x^2$$x$$x^2$$x$$x^{1.999}$

Oto przykład wyjaśniający to (i konkretny przykład dobrej odpowiedzi Davida).

Załóżmy, że masz algorytmu, który jest podany na wejściu tablicę liczb całkowitych . Algorytm skanuje tablicę i inkrementuje licznik początkowo ustawiony na zero za każdym razem, gdy widzi element, który jest parzystą liczbą całkowitą. Można udowodnić uruchamia algorytm powiedzmy O ( N 3 ) czasu, w którym n oznacza liczbę elementów A . Ale możemy również podać ściślejszą granicę i powiedzieć, że biegnie w czasie O ( n ) . Ta granica jest asymptotycznie ciasna: w rzeczywistości, ponieważ odczyt danych zajmuje już czas Ω ( n ) , możemy być bardziej precyzyjni i powiedzieć, że algorytm zajmuje$A$$O(n^3)$$n$$A$$O(n)$$\Omega(n)$ czas.$\Theta(n)$