Dlaczego uczy się Big O zamiast Big Theta?

21

Notacja Big O zapewnia górną granicę funkcji, podczas gdy Big Theta zapewnia ścisłą granicę. Uważam jednak, że notacja Big O jest zwykle (i nieformalnie) nauczana i stosowana, gdy naprawdę mają na myśli Big Theta.

np. „Quicksort to O (N ^ 2)” może przekształcić się w znacznie silniejsze zdanie „Quicksort to Θ (N ^ 2)”

Chociaż użycie Big O jest technicznie poprawne, czy bardziej powszechne stosowanie Big Theta nie byłoby bardziej wyraziste i nie prowadziło do mniejszego zamieszania? Czy jest jakiś historyczny powód, dla którego ten Big O jest częściej używany?

Notatki Wikipedii :

Nieformalnie, szczególnie w informatyce, często dopuszcza się nadużywanie notacji Big O w celu opisania asymptotycznej ścisłej więzi, w której użycie notacji Big Theta może być bardziej odpowiednie w danym kontekście.

notation big-o big-theta tskuzzy
źródło
3
Wiem, że tak naprawdę nie dotyczy to pytania, ale quicksort nie jest theta (N ^ 2). To O (N ^ 2).
jsternberg
Big O jest tym, co powinni wiedzieć początkujący / spoza CS. Big Theta jest tym, co jest zawarte we wstępie do algorytmów, które nie będą podejmowane przez każdą specjalizację. Ci, którzy mieli klasę algorytmów, mogą głębiej wczytać zapis Big O, jeśli chcą. Nie jestem pewien, do czego odnosi się cytat z Wikipedii. Dzięki publikacjom akademickim poderżniesz sobie gardło na konferencji, jeśli pomylisz Big O i Big Theta. Niektórzy ludzie spędzają całe życie na pogoni za Theta, a to są trudne problemy.
Job
@ jsternberg Technicznie masz rację. To także prawda, ale bez znaczenia: „Quicksort w każdym przypadku (najgorsze, najlepsze, ...) to O (n ^ 100). Ale zgadzam się z OP, powinno być dokładniej: Najgorszym przypadkiem QuickSort jest Theta (N ^ 2), najlepszym przypadkiem QuickSort jest Theta (NlogN), ponieważ w każdym przypadku otrzymamy inną funkcję
Eldar

Odpowiedzi:

26

Ponieważ zazwyczaj interesuje Cię najgorszy przypadek podczas analizy wydajności. Zatem znajomość górnej granicy jest wystarczająca.

Gdy działa on szybciej niż oczekiwano dla danego wejścia - to dobrze, nie jest to punkt krytyczny. To w większości nieistotna informacja.

Niektóre algorytmy, jak zauważył @Peter Taylor, wcale nie są ściśle powiązane. Zobacz na przykład quicksort, który jest O (n ^ 2) i Omega (n).

Co więcej, ciasne granice są często trudniejsze do obliczenia.

Zobacz też:

Sokół
źródło
6
Ale Big O niekoniecznie odpowiada wydajności w najgorszym przypadku. Mógłbym powiedzieć, że quicksort działa w O (2 ^ n) i być w 100% poprawny. Byłoby znacznie bardziej znaczące, jeśli powiem, że algorytm X działa w Theta (N ^ 2), a nie w O (N ^ 2).
tskuzzy 08.08.11
Ponadto ścisłe granice są prawie zawsze obliczane podczas analizy algorytmów, a nie tylko górna granica. Pytam, dlaczego ludzie nie używają o wiele bardziej ekspresyjnej notacji theta, kiedy mogą.
tskuzzy 08.08.11
9
Powiedziałem wam, dlaczego większość programistów tego nie używa. Jesteśmy leniwi i nie potrzebujemy tyle dokładności. Jeśli chcesz, nikt nie powstrzyma cię przed użyciem dużej theta. Śmiało, zrób to. Twój wybór algorytmu najprawdopodobniej nie skorzysta z tego tak bardzo. Nigdy nie słyszałem o programatorze mylonym przez wielką notację O. Ja też nie uważam tego za mylące.
Falcon,
9

Jednym z powodów jest to, że istnieje wiele przypadków, w których Θ po prostu nie jest znany. Na przykład, mnożenie macierzy wynosi O (n ^ 2,376), ale nie ma znanych ścisłych ograniczeń. Oczywiście, o ile mogę powiedzieć, że jest mocno związany na mnożenie macierzy, ale nie znamy jego wartość.

MSalters
źródło
Ale to byłby limit czasu działania problemu, a nie konkretnego algorytmu. Podczas gdy mnożenie macierzy w ogóle można rozwiązać szybciej niż czas sześcienny, naiwny algorytm wynosi Θ (n ^ 3) bez względu na wszystko.
tskuzzy
5
@tskuzzy, weź Quicksort. Nie ma powiązania z Theta, ponieważ jest to O (n ^ 2) i Omega (n).
Peter Taylor,