Matematycznie rozumiem $ f (n) \ in O (g (n)) $: $ f (n) $ nie rosną szybciej niż $ g (n) $. Bardziej formalnie, $ \ istnieje c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Podobnie, $ f (n) \ in \ Theta (g (n)) $ oznacza, że $ f (n) $ rośnie w przybliżeniu tak szybko, jak $ g (n) $. czyli $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
Nie rozumiem, dlaczego ludzie używają dużego Oh w czasie działania algorytm? Czy nie powinniśmy używać dużej Theta. Kiedy mówimy „Czas działania” algorytmu, mamy na myśli najgorszy czas działania, czyli $ T (n) = max \ {ALG (x): | x | = n \} $.
Na przykład: czas trwania wyszukiwania liniowego w najgorszym przypadku na wejściu o rozmiarze $ n $ ($ n $ elementów i wartość docelowa) to $ \ Theta (n) $ i $ O (n) $, ale $ \ Theta (n) $ daje więcej informacji. Dlaczego więc książki algorytmów używają $ O (n) $, a nie $ \ Theta (n) $.
Komentarze
- Często ' s, ponieważ po prostu możemy ' t uzyskać ścisłe ograniczenie big-theta w czasie działania algorytmu. Jeśli algorytm jest wystarczająco skomplikowany, może się zdarzyć, że najlepsze, co możemy zrobić, to powiedzieć, że czas jego wykonania to, powiedzmy, $ O (n ^ {n!}) $, Gdzie w rzeczywistości może to być $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Przyczyny historyczne.
- ” Czego nie robię ' nie rozumiem, dlaczego ludzie używają dużego Oh do czasu działania algorytmu? Czy nie powinniśmy ' używać dużej Theta. ” – Tak. Czekaj, nie, powinniśmy sformułować jeszcze dokładniejsze stwierdzenia. Ale jeśli muszę wybrać, tak, $ \ Theta $!
Odpowiedź
Widzę dwa powody, dla których ludzie wolą Big Oh od Big Theta:
- Złożoność algorytmu w czasie wykonywania jest niekoniecznie definiowana jako najgorsza złożoność środowiska wykonawczego. Możesz również zobaczyć to jako środowisko wykonawcze w dowolnej instancji o długości $ n $. Następnie, jeśli napiszesz na przykład, że czas działania $ t (n) $ algorytmu jest w $ \ mathcal {O} (n ^ 2) $ oznacza to, że niezależnie od wybranej długości wejściowej $ n $, zawsze będzie rosnąć asymptotycznie wolniej niż funkcja $ c \ cdot n ^ 2 $ dla jakiejś stałej $ c $ – więc oczywiście robimy oświadczenie o najgorszym przypadku wykonania.
- Czasami, gdy analizujesz środowisko wykonawcze złożoność algorytmu, którego nie masz pewności, czy najgorszy przypadek, który podajesz, jest naprawdę wąski. Weźmy na przykład złożoność mnożenia macierzy w czasie wykonywania . Wciąż nie jest jasne, czy środowisko wykonawcze $ n ^ {2.3728639} $ jest naprawdę najgorszym przypadkiem. Dlatego też wiadomo, że środowisko wykonawcze znajduje się w $ \ mathcal {O} (n ^ {2.3728639}) $, podczas gdy to ” Nie jesteś pewien, czy znajduje się w $ \ Theta (n ^ {2.3728639}) $.
Ale także masz rację, że w niektórych przypadkach byłoby lepiej zapewnić Big Theta związane niż Big Oh.
Komentarze
- Reklama 1: Czytelnicy, bądźcie ostrożni nie czytać za dużo o tym !
Odpowiedz
(Niechlujna) górna granica jest łatwiejsza do udowodnienia niż ścisła górna granica, nie mówiąc już o górnych i dolnych granicach.
Czas wykonania niektórych algorytmów nie może „t mają taką samą funkcję jak górna / dolna granica. Na przykład. proste algorytmy sortowania to $ O (n ^ 2) $, ale mają dolną granicę $ \ Omega (n) $.
Niektórzy nalegają na uzyskanie wydajności w kategoriach asymptotycznych poprzez $ \ sim $, gdzie $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(powiedzmy jako średni lub najgorszy przypadek pod względem liczby krytycznych operacji, takich jak porównania podczas sortowania). To znaczy poruszaj się w pokoju, ale żadne (prawdopodobnie ogromne) stałe nie zostały zmiecione pod dywan.
Komentarze
- Kiedy odnosimy się do ” runtime „, odnosimy się do czegoś takiego jak czas działania w najlepszym przypadku, czas działania w najgorszym przypadku i czas działania w przypadku średnim. Np .: Quicksort ma czas działania $ \ Theta (n ^ 2) $ w najgorszym przypadku i $ \ Theta (n) $ w najlepszym przypadku. Asymptotyki są zdefiniowane po prawej stronie funkcji.
Odpowiedź
Jeśli duże-Theta można użyć zamiast dużych- Och, powinno się go używać, chyba że powoduje to niepotrzebne trudności w zrozumieniu. Istnieją pewne subtelne przypadki, kiedy duże-Theta nie może być użyte zamiast dużego-Oh, np .:
Rozważmy następujący problem: sortuj tablice o parzystej długości. Program rozwiązujący ten problem mógłby wyglądać następująco: jeśli długość tablicy jest nieparzysta, natychmiast zakończ, jeśli długość tablicy jest parzysta, wykonaj sortowanie bąbelkowe. Jaki jest najgorszy czas działania tego algorytmu?
Na pewno jest to $ O (n ^ 2) $, ale NIE jest to $ \ Omega (n ^ 2) $ w sensie $ \ Omega $ jest zwykle definiowana. Zamiast tego jej najgorszy czas działania to „$ \ Omega (n ^ 2) $ nieskończenie często”, że tak powiem (ostrzeżenie: niestandardowa terminologia).
Odpowiedź
W odpowiedzi na pytanie „dlaczego książki o algorytmach używają dużego-Oh, a nie Theta”:
Big-Oh jest używane do analizy najgorszego przypadku, a Big-Omega jest używane tylko dla najlepszego przypadku. Ale analizując pod kątem Big-Theta, mówimy jednocześnie o obu Big-Oh & Big-Omega.
ie. W przypadku Big-Theta konieczne jest, aby Big-Oh == Big-Omega, w przeciwnym razie nie możemy mówić o Big-Theta.
Więc gdziekolwiek (książka / jakikolwiek dokument) widzisz użycie Big-Theta, dają złożoność obu Big-Oh & Big-Omega (i obie są równe). Ale w wielu przypadkach nie są równe, wtedy używamy tylko Big- Och, tylko w najgorszym przypadku.