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

100

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.

Adeel Ansari
źródło

Odpowiedzi:

155

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).

Chris Bunch
źródło
7
Och… Teraz termin „ciasne związanie” wydaje mi się całkiem zrozumiały. Dzięki Chris. Głupi ja, może spodziewałem się jakiegoś złożonego pomysłu. :)
Adeel Ansari
6
Tak, istnieje wiele wymyślnych notacji, ale nie jest to zbyt skomplikowane, gdy już złapiesz ją za pas.
Chris Bunch
4
Ten swobodnie dostępny dokument firmy Virginia Tech wyjaśnia na przykładach różnice w wydajności między algorytmami o różnym stopniu złożoności i krótko wyjaśnia analizę asymptotyczną: people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf
Alan
Co masz na myśli, mówiąc: „Algorytm przyjmujący Theta (n log n) jest daleko preferencyjny, ponieważ wymaga co najmniej n log n (Omega n log n) i nie więcej niż n log n (Big O n log n).”, Jak in, czy jest to dokładna złożoność algorytmu, jak napisałeś, co najmniej Omega (nlogn) i przy max BigO (nlogn)?
Nikhil Verma
1
W prostych słowach możemy nazwać: górną granicę (Big (O)) jako najgorszy przypadek? mocno związany jak w przeciętnym przypadku? dolna granica (Omega) jako najlepszy przypadek?
Revanth
113

Θ 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 2 ), O (n 3 ) i O (2 n ), 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.

Bill the Lizard
źródło
11
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every case- Wygląda na to, że większość ludzi w świecie komputerów jest leniwa tylko dlatego, że wszyscy w większości mówią tylko o złożoności Big O.
RBT
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every caseNa wypadek, gdyby ktoś się z tym pomylił: Dla tego rodzaju funkcji, które nie są asymptotycznie ciasne, używana jest notacja small-o. Przykład: - Ograniczenie 2n ^ 2 = O (n ^ 2) jest asymptotycznie ciasne, ale ograniczenie 2n = O (n ^ 2) nie. Czytaj więcej: stackoverflow.com/questions/1364444/ ...
Dragos Strugar
18

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.

Charlie Martin
źródło
Teraz czytam rodzinę notacji Bachmann-Landau. Dzięki Charlie, byłem tam wcześniej, ale wróciłem bez przechodzenia do jego długości.
Adeel Ansari
Hej, dobrze jest co jakiś czas odświeżać kompozycje doktoranckie.
Charlie Martin
Zauważ, że notacja big-O Landaua nie ogranicza się do złożoności algorytmicznej.
Charlie Martin
To źle wygląda. W pierwszym wierszu powinno brzmieć „Jeśli masz coś, co jest O (g (n))”, czyli gzamiast f, a resztę można pozostawić tak, jak jest. To samo dotyczy drugiej linii: powinno to być „Jeśli masz coś, co jest Ω (g (n))”. Czy możesz sprawdzić dwukrotnie?
Fabio mówi Przywróć Monikę
Cały temat jest tak pokręcony, że ktoś z tym kredytem również może się pomylić: D Żarty na bok, ktoś musi poprawić tę odpowiedź. To dezorientuje ludzi (bardzo mi to zrobiło).
Rad
5

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 1 g (n) ≤ f (n) ≤ c 2 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 1 i c 2 są stałymi.

to samo menu
źródło
1
jeśli tablica jest posortowana, granica nadal będzie O (n)
Arun Aravind,
2
@ArunAravind Czy możesz wyjaśnić dlaczego?
nbro
3

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).

PolyThinker
źródło
Czy możemy więc powiedzieć, że Ω to najlepszy przypadek, a O to najgorszy? . .. i czy powinniśmy zamienić terminy odpowiednio na najlepszy i najgorszy przypadek?
Adeel Ansari
Najlepszy przypadek to O (1) dla każdego problemu?
Zach Langley,
1
@Adeel, no, Theta i O mogą odnosić się zarówno do przypadku średniego, jak i do najgorszego. @Zach, cóż, nie do końca. Dzięki za zwrócenie uwagi.
PolyThinker,
0

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.

Brakuje Finna
źródło
0

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ę.

PI Gogole
źródło
-2

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.

BOBBY Z
źródło
2
Nie powinieneś odpowiadać na stare pytania, jeśli twoja odpowiedź nie dodaje nic do już zaakceptowanych odpowiedzi.
alestanis