Czy ktoś mógłby wytłumaczyć Big O kontra Big Omega vs Big Theta?

Question

Powiel możliwe:
Big Theta Notation - what exactly does big Theta represent?

rozumiem w teorii, jak sądzę, ale co mam problemy chwytania jest zastosowanie trzech.

W szkole zawsze używaliśmy Big O do oznaczania złożoności algorytmu. Sortowanie bąbelkowe było na przykład O (n^2).

Teraz po przeczytaniu trochę więcej teorii dostaję, że Big Oh nie jest jedyną miarą, są co najmniej dwa inne interesujące.

Ale tu jest moje pytanie:

Big O to górna związana, Big Omega jest dolną granicą, a Big Theta jest mieszanką dwóch. Ale co to znaczy koncepcyjnie? Rozumiem, co to znaczy na wykresie; Widziałem milion takich przykładów. Ale co to znaczy dla złożoności algorytmu? W jaki sposób miesza się "górna granica" lub "dolna granica"?

Chyba po prostu nie otrzymuję wniosku. I rozumieć, że jeśli pomnożone przez niektóre stałej c, że jeśli po pewnym wartość n_0 f (x) jest większa niż G (x), f (x) jest traktowany O (G (x)). Ale co to właściwie oznacza? Dlaczego mielibyśmy pomnożyć f (x) przez jakąś wartość c? Do diabła, myślałem, że wielokrotność notacji Big O nie ma znaczenia.

Answer 1

Duża notacja O i jej krewni, duża Theta, duża Omega, mała oi mała omega to sposoby mówienia o tym, jak funkcja zachowuje się w punkcie granicznym (na przykład, gdy zbliżamy się do nieskończoności, ale także przy zbliżaniu się do 0 itd.), nie mówiąc już nic więcej o tej funkcji. Są one powszechnie używane do opisu bieżącej przestrzeni i czasu algorytmów, ale można je również zobaczyć w innych obszarach matematyki dotyczących zachowań asymptotycznych.

Częściowo intuicyjne określenie jest następujący:

funkcja g (x), mówi się, że O (F (x)) jeśli "z pewnym punktem", g (x) jest mniejsza niż ok * f (x), gdzie c jest trochę stałe.

Inne definicje są podobne, Theta domaga się, aby g (x) było między dwiema stałymi wielokrotnościami f (x), Omega wymagająca g (x)> c * f (x), a małe wersje wymagają, aby to było prawda dla wszystkich takich stałych.

Ale dlaczego jest interesujące powiedzieć, na przykład, że algorytm ma czas działania O (n^2)?

To interesujące, ponieważ w informatyce teoretycznej najbardziej interesuje nas zachowanie algorytmów dla dużych wejść. Jest to prawdą, ponieważ na małych wejściach algorytm czas działania może się znacznie różnić w zależności od implementacji, kompilacji, sprzętu i innych rzeczy, które nie są naprawdę interesujące przy teoretycznej analizie algorytmu.

Szybkość wzrostu zależy jednak zazwyczaj od charakteru algorytmu, a aby go poprawić, należy uzyskać głębszy wgląd w problem, który próbujesz rozwiązać. Dzieje się tak na przykład w przypadku algorytmów sortowania, w których można uzyskać prosty algorytm (sortowanie bąbelkowe) w O (n^2), ale aby poprawić to do O (n log n) potrzebny jest naprawdę nowy pomysł , takie jak wprowadzone w Sortowanie scalania lub Sortowanie sterty.

Z drugiej strony, jeśli masz algorytm działający dokładnie w 5 sekund i inny, który działa w 1000n sekund (na przykład różnica między długim ziewnięciem a przerwą uruchamiania dla n = 3), kiedy dojdziesz do n = 1000000000000, różnica w skali wydaje się mniej ważna. Jeśli masz algorytm, który zajmuje O (log n), musisz jednak czekać log (1000000000000) = 12 sekund, być może pomnożony przez jakąś stałą, zamiast prawie 317 098 lat, które, bez względu na to, jak duża jest stała jest, jest zupełnie inną skalą.

Mam nadzieję, że dzięki temu sprawy staną się nieco jaśniejsze. Powodzenia z Twoimi studiami!