Jaka jest różnica między dolną granicą a ciasną granicą?

W odniesieniu do tej odpowiedzi , czym jest Theta (mocno związana)?

Omega to dolna granica, całkiem zrozumiała, minimalny czas, jaki może zająć algorytm. Wiemy, że Big-O dotyczy górnej granicy, czyli maksymalnego czasu, jaki może zająć algorytm. Ale nie mam pojęcia o Theta.

Duże O to górna granica, podczas gdy Omega to dolna granica. Theta wymaga zarówno Big O, jak i Omegi, dlatego określa się ją jako ciasne wiązanie (musi to być zarówno górna, jak i dolna granica).

Na przykład wykonanie algorytmu Omega(n log n)zajmuje co najmniej n log nczas, ale nie ma górnej granicy. Podejmowanie algorytmu Theta(n log n)jest znacznie preferencyjne, ponieważ zajmuje co najmniej n log n (Omega n log n) i nie więcej niż n log n (Big O n log n).

Θ notacja (theta notacja) nazywa mocno związana, ponieważ jest bardziej dokładne niż O-zapisu i co-zapisu (omega notacji).

Gdybym był leniwy, mógłbym powiedzieć, że wyszukiwanie binarne na posortowanej tablicy to O (n ² ), O (n ³ ) i O (2 ⁿ ), i technicznie byłbym poprawny w każdym przypadku. Dzieje się tak, ponieważ notacja O określa tylko górną granicę , a wyszukiwanie binarne jest ograniczone po górnej stronie przez wszystkie te funkcje, ale niezbyt ściśle. Te leniwe szacunki byłyby bezużyteczne .

Notacja Θ rozwiązuje ten problem poprzez połączenie notacji O i notacji Ω. Jeśli powiem, że wyszukiwanie binarne to Θ (log n), dostaniesz bardziej precyzyjne informacje. Mówi ci, że algorytm jest ograniczony z obu stron przez daną funkcję, więc nigdy nie będzie znacznie szybszy ani wolniejszy niż podano.

Jeśli masz coś, co jest O (f (n)) , oznacza to, że jest k , g (n) takie, że f (n) ≤ kg (n) .

Jeśli masz coś, co jest Ω (f (n)) , oznacza to, że jest k , g (n) takie, że f (n) ≥ kg (n) .

A jeśli masz coś z O (f (n)) i Ω (f (n)) , to jest to Θ (f (n) .

Artykuł w Wikipedii jest przyzwoity, choć trochę gęsty.

Asymptotyczna górna granica oznacza, że ​​dany algorytm jest wykonywany przez maksymalny czas, w zależności od liczby wejść.

Jako przykład weźmy algorytm sortowania. Jeśli wszystkie elementy tablicy są w porządku malejącym, sortowanie ich zajmie trochę czasu O(n), pokazując złożoność górnej granicy. Jeśli tablica jest już posortowana, wartość będzie O(1).

Zwykle O-notationjest używany dla górnej granicy złożoności.

Asymptotycznie ścisła granica (c ₁ g (n) ≤ f (n) ≤ c ₂ g (n)) przedstawia średnią złożoność związaną dla funkcji, mającą wartość między granicami granicznymi (granica górna i granica dolna), gdzie c ₁ i c ₂ są stałymi.

Zwroty minimalny czas i maksymalny czas są tutaj nieco mylące. Kiedy mówimy o dużych notacjach O, nie chodzi o rzeczywisty czas, który nas interesuje, ale o to, jak rośnie czas, gdy nasz rozmiar wejściowy staje się większy. Zwykle jest to średni lub najgorszy czas, o którym mówimy, a nie najlepszy przypadek , który zwykle nie ma znaczenia w rozwiązywaniu naszych problemów.

Na przykładzie wyszukiwania w tablicy w zaakceptowanej odpowiedzi na inne pytanie. Czas potrzebny do znalezienia określonej liczby na liście o rozmiarze n wynosi średnio n / 2 * some_constant. Jeśli potraktujesz to jako funkcję f(n) = n/2*some_constant, nie rośnie szybciej niż g(n) = nw sensie podanym przez Charliego. Ponadto rośnie nie wolniej niż g(n)jeden z nich. Stąd, g(n)jest w rzeczywistości zarówno górną, jak i dolną granicą f(n)w notacji Big-O, więc złożoność wyszukiwania liniowego wynosi dokładnie n , co oznacza, że ​​jest to Theta (n).

W tym względzie wyjaśnienie w przyjętej odpowiedzi na drugie pytanie nie jest do końca poprawne, twierdząc, że O (n) jest górną granicą, ponieważ algorytm może działać w stałym czasie dla niektórych danych wejściowych (jest to najlepszy przypadek , o którym wspomniałem powyżej, co nie jest tym, co chcielibyśmy wiedzieć o czasie działania).

Gdybym był leniwy, mógłbym powiedzieć, że wyszukiwanie binarne na posortowanej tablicy to O (n2), O (n3) i O (2n) i technicznie byłbym poprawny w każdym przypadku.

Możemy użyć o-notacji („little-oh”), aby oznaczyć górną granicę, która nie jest asymptotycznie ścisła. Zarówno duże, jak i małe, są podobne. Ale duże-och jest prawdopodobnie używane do definiowania asymptotycznie ścisłej górnej granicy.

Dokładnie dolna granica lub $ \ omega $ bfon f (n) oznacza zbiór funkcji, które są asymptotycznie mniejsze lub równe f (n) tj. U g (n) ≤ cf (n) $ \ dla wszystkich $ `un≥ n 'Dla jakiegoś c, n' $ \ in $ $ \ Bbb {N} $

A górna granica lub $ \ mathit {O} $ na f (n) oznacza zbiór funkcji, które są asymptotycznie większe lub równe f (n), co matematycznie mówi,

$ g (n) \ ge cf (n) \ for all n \ ge n '$, dla niektórych c, n' $ \ in $ $ \ Bbb {N} $.

Teraz $ \ Theta $ jest przecięciem dwóch zapisanych powyżej

$\theta $

Na przykład, jeśli algorytm wygląda następująco: „dokładnie $ \ Omega \ left (f (n) \ right $”), to lepiej powiedzieć, że jest to $ \ Theta \ left (f (n) \ right) $.

Lub możemy też powiedzieć, że daje nam to rzeczywistą prędkość, przy której $ \omega $daje nam najniższą granicę.

Podstawowa różnica między

Zablokować cytat

asymptotycznie górna granica i asymptotycznie ciasna Asym. górna granica oznacza dany algorytm, który może być wykonywany w maksymalnym czasie zależnym od liczby wejść, np. w sortowaniu algorytmu, jeśli wszystkie elementy tablicy (n) są w porządku malejącym, a następnie rosnąco zajmie czas wykonania O (n), co pokazuje złożoność górnej granicy, ale jeśli są już posortowane, zajmie to om (1). Więc ogólnie używaliśmy notacji "O" dla górnej granicy złożoności.

Asym. ścisłe ograniczenie pokazuje, że np. (c1g (n) <= f (n) <= c2g (n)) pokazuje ścisłe ograniczenie, tak że funkcja ma wartość pomiędzy dwoma ograniczeniami (górną i dolną granicą), dając przeciętny przypadek.