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.
Odpowiedzi:
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 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.
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.
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/ ...
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.
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?
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.
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.