Jak O i Ω odnoszą się do najgorszego i najlepszego przypadku?

33

Dzisiaj omawialiśmy na wykładzie bardzo prosty algorytm znajdowania elementu w posortowanej tablicy za pomocą wyszukiwania binarnego . Poproszono nas o określenie jego asymptotycznej złożoności dla szeregu $n$ elementów.

Mój pomysł polegał na tym, że jest to wyraźnie $O(\log n)$ lub $O(\log_2 n)$ aby być bardziej szczegółowym, ponieważ $\log_2 n$ to liczba operacji w najgorszym przypadku. Ale mogę zrobić lepiej, na przykład, jeśli uderzę szukany element za pierwszym razem - wówczas dolna granica to $\Omega(1)$ .

Wykładowca przedstawił rozwiązanie jako $\Theta(\log n)$ ponieważ zwykle uwzględniamy tylko najgorsze dane wejściowe dla algorytmów.

Ale kiedy rozważamy tylko najgorsze przypadki, jaki jest sens notowania $O$ i $\Omega$ gdy wszystkie najgorsze przypadki danego problemu mają tę samą złożoność ( $\Theta$ byłoby wszystkim, czego potrzebujemy, prawda?).

Czego tu brakuje?

— Smajl
źródło

@Smaji: Co rozumiesz przez „Ale gdy rozważamy tylko najgorsze przypadki, jaki jest sens posiadania dużego O i dużej notacji Omega, gdy wszystkie najgorsze przypadki mają + - tę samą złożoność (Theta byłaby wszystkim, czego potrzebujemy, prawda?).” proszę wyjaśnij to.

— tanmoy

@Smajl: Myślę, że twoje pytanie brzmi: jaka jest konieczność notacji Big O i Big Omega w analizie algorytmów? mam rację?

— tanmoy

5

O (\log_{2} n)

$O(\log_2 n)$ nie jest bardziej szczegółowe niż

O (\log n)

$O(\log n)$ , oznaczają one tę samą klasę funkcji.

— Raphael

jest tym samym, co

dlatego 2 oznacza tylko czynnik, który można usunąć (podobnie jak inne czynniki w dużych -O.

l o g_{2} (n)

$log_2(n)$

l o g (b) / l o g (2) \times l o g_{b} (n)

$log(b)/log(2) × log_b(n)$

— ctrl-alt-delor

39

Notacja Landaua oznacza asymptotyczne granice funkcji . Zobacz tutaj wyjaśnienie różnic między , i . $O$ $\Omega$ $\Theta$

Czas najgorszy, najlepszy, średni lub nazwa użytkownika to odrębne funkcje środowiska wykonawczego: jedna dla sekwencji najwyższego czasu wykonywania dla danego , jedna dla najniższej itd. $n$

Same w sobie nie mają ze sobą nic wspólnego. Definicje są niezależne. Teraz możemy iść do przodu i formułować asymptotyczne granice funkcji czasu wykonywania: górny ( ), dolny ( ) lub oba ( ). Możemy to zrobić w najgorszym, najlepszym lub innym przypadku. $O$ $\Omega$ $\Theta$

Na przykład, w poszukiwaniu binarnego możemy uzyskać najlepsze case wykonania asymptotycznej z i najgorszy asymptotycznej z . $\Theta(1)$ $\Theta(\log n)$

— Raphael
źródło

Najważniejsze dla mnie jest to, że możemy przeprowadzić analizę najgorszego i najlepszego przypadku dowolnego z asymptotycznych funkcji ograniczonych. Dla mnie pokazuje to niezależność analizy Big O od najgorszego przypadku. Dzięki!

— Patrick

1

@Patrick Niezupełnie. Po pierwsze, decydujesz, czy chcesz analizować najgorszy, średni czy najlepszy przypadek. Następnie wymyślisz funkcję kosztu (lub możliwie najlepsze przybliżenie). Dopiero wtedy przyjmujesz asymptotyki, jeśli w ogóle.

— Raphael

17

Rozważ następujący algorytm (lub procedurę, fragment kodu lub cokolwiek innego):

Contrive(n)
1. if n = 0 then do something Theta(n^3)
2. else if n is even then
3.    flip a coin
4.    if heads, do something Theta(n)
5.    else if tails, do something Theta(n^2)
6. else if n is odd then
7.    flip a coin
8.    if heads, do something Theta(n^4)
9.    else if tails, do something Theta(n^5)

Jakie jest asymptotyczne zachowanie tej funkcji?

W najlepszym przypadku (gdzie jest parzyste), czas działania wynosi i , ale nie $n$ $\Omega(n)$ $O(n^2)$ $\Theta$ niczego.

W najgorszym przypadku (gdzie jest nieparzyste), czas działania wynosi i , ale nie $n$ $\Omega(n^4)$ $O(n^5)$ $\Theta$ niczego.

W przypadku środowisko wykonawcze wynosi $n = 0$ $\Theta(n^3)$ .

Jest to trochę wymyślony przykład, ale tylko w celu wyraźnego wykazania różnic między związkiem a sprawą. Można mieć rozróżnienie nabierają znaczenia procedur całkowicie deterministycznych, jeżeli działalność jesteś wykonujący nie ma żadnych znanych granic. $\Theta$

— Patrick87
źródło

1

Aby uczynić to deterministycznym, podziel według

przypadków.

n mod 4

$n \bmod 4$

— vonbrand,

4

Niekoniecznie. W tym przypadku, a mianowicie wyszukiwanie binarne na posortowanej tablicy, można zauważyć, że: (a) wyszukiwanie binarne zajmuje co najwyżej kroki; (b) istnieją dane wejściowe, które faktycznie wymuszają tak wiele kroków. Jeśli więc jest czasem wykonywania dla danych binarnych o najgorszym przypadku, można powiedzieć, że $[\log n + 1]$ $T(n)$ $T(n) = \Theta(\log n)$ .

Z drugiej strony dla innych algorytmów możesz nie być w stanie wypracować $T(n)$ dokładnie wyliczyć , w którym to przypadku możesz mieć przerwę między górną i dolną granicą dla czasu pracy na wejściu w najgorszym przypadku.

Teraz przy przeszukiwaniu posortowanej tablicy jest coś więcej, co oznacza, że każdy algorytm przeszukiwania posortowanej tablicy musi sprawdzić $[\log n + 1]$ $S\subset [n]$ $|S|$ $2$

— Louis
źródło

1

$O$ $\Theta$ $% T(n)=n^{2}+n+2$ $T(n)=O(n^{2})$ $T(n)=\Theta (n^{2})$ $O$ $\Theta$ $% \Omega$ $O$ $\Theta$

$O$ $\Theta$ $\Theta$ $\Theta (1)$ $% \Theta (\log n)$ $O$ $O(\log n)$ $\Theta$ $O$ , podczas gdy odwrotność niekoniecznie jest prawdziwa.

— Hamed Nassar
źródło

O (\log n)

$O(\log n)$

Θ (\log n)

$Θ(\log n)$

@ Rafael Odsyłam cię do definicji dwóch zapisów. Co więcej, zdaj sobie sprawę, że są one używane do klasyfikowania asymptotycznej „stopy wzrostu” czasu działania, a nie samego czasu działania, jak wynika z różnych odpowiedzi i komentarzy.

— Hamed Nassar,