Skąd wiadomo, jakiego zapisu analizy złożoności czasu użyć?

W większości klas algorytmów wprowadzających wprowadzane są notacje takie jak (Big O) i , a uczeń zazwyczaj uczy się korzystania z jednej z nich w celu znalezienia złożoności czasowej. $O$ $\Theta$

Istnieją jednak inne oznaczenia, takie jak , i . Czy są jakieś konkretne scenariusze, w których jedna notacja byłaby lepsza od innej? $o$ $\Omega$ $\omega$

— Jack H.
źródło

nie jest to tak bardzo korzystne, jak ma zastosowanie ...

— wer

Odpowiedzi:

Odwołujesz się do notacji Landaua . Nie są to różne symbole tej samej rzeczy, ale mają zupełnie inne znaczenie. To, które jest „preferowane”, zależy całkowicie od pożądanego stwierdzenia.

$f \in \cal{O}(g)$ oznacza, że rośnie maksymalnie tak szybko jak , asymptotycznie i do stałego współczynnika; pomyśl o tym jak o . jest bardziej rygorystyczną formą, tj . . $f$ $g$ $\leq$ $f \in o(g)$ $<$

$f \in \Omega(g)$ ma symetryczne znaczenie: rośnie co najmniej tak szybko, jak . jest bardziej surowym kuzynem. Widać, że jest równoważne . $f$ $g$ $\omega$ $f \in \Omega(g)$ $g \in \cal{O}(f)$

$f \in \Theta(g)$ oznacza, że rośnie tak szybko, jak ; formalnie . (równość asymptotyczna) to jego silniejsza forma. Często mamy na myśli gdy używamy . $f$ $g$ $f \in \cal{O}(g) \cap \Omega(g)$ $f \sim g$ $\Theta$ $\cal{O}$

Zwróć uwagę, że i jego rodzeństwo są klasami funkcji . Ważne jest, aby być bardzo świadomym tego i ich dokładnych definicji - które mogą się różnić w zależności od tego, kto mówi - podczas wykonywania z nimi „arytmetyki”. $\cal{O}(g)$

Podczas sprawdzania rzeczy staraj się pracować z precyzyjną definicją. Istnieje wiele definicji symboli Landaua (wszystkie z tą samą podstawową intuicją), z których niektóre są równoważne w niektórych zestawach funkcji, ale nie w innych.

Sugerowane czytanie:

Jeśli interesuje Cię rygorystyczne i rzetelne stosowanie notacji Landaua, możesz zainteresować się ostatnimi pracami Rutanena i in. [1] Formułują niezbędne i wystarczające kryteria dla asymptotycznej notacji, gdy używamy ich w algorytmach, pokazują, że wspólna definicja ich nie spełnia i zapewniają (w rzeczywistości) wykonalną definicję.

Ogólna definicja notacji O do analizy algorytmicznej autorstwa K. Rutanena i in. (2015)

— Raphael
źródło

Chcę tylko zaznaczyć, że chociaż działa jak a działa jak , istnieją różnice; nie jest trudno znaleźć funkcje i takie jak i .

O

$\mathcal{O}$

\leq

$\le$

Ω

$\Omega$

\geq

$\ge$

g

$g$

f

$f$

f \notin O (g)

$f \not\in \mathcal{O}(g)$

f \notin Ω (g)

$f \not\in \Omega(g)$

— Zach Langley,

+1 za wzmiankę o klasach funkcji. Rzeczy takie jak i pojawiają się wszędzie w gazetach i książkach, co może być mylące dla osób, które napotykają te notacje po raz pierwszy.

o (1)

$o(1)$

Ω (2^{n})

$\Omega(2^n)$

— Janoma

@ZachLangley To, co mówisz, jest bardzo prawdziwe. Tutaj nie ma całkowitego zamówienia. Prawdopodobnie niebezpieczne jest w ogóle , ale myślę, że służy to budowaniu intuicji.

\leq

$\leq$

— Raphael

Big O: górna granica

„Big O” ( ) jest zdecydowanie najczęstszym. Kiedy analizujesz złożoność algorytmu, przez większość czasu liczy się górna granica tego, jak szybko rośnie czas pracy¹, gdy rośnie wielkość danych wejściowych. Zasadniczo chcemy wiedzieć, że uruchomienie algorytmu nie zajmie „zbyt długo”. Nie możemy tego wyrazić w rzeczywistych jednostkach czasu (sekundach), ponieważ zależałoby to od dokładnej implementacji (sposobu pisania programu, jakości kompilatora, szybkości procesora komputera,…). Oceniamy więc, co nie zależy od takich szczegółów, czyli ile czasu zajmuje uruchomienie algorytmu, gdy dostarczymy mu większe dane wejściowe. I zależy nam przede wszystkim na tym, kiedy możemy być pewni, że program został ukończony, dlatego zwykle chcemy wiedzieć, że zajmie to tak długo taki lub mniej czas. $O$

Stwierdzenie, że algorytm ma czas działania dla rozmiaru wejściowego oznacza, że istnieje pewna stała tak że algorytm wykonuje się co najwyżej w krokach , tj. Czas działania algorytmu rośnie co najwyżej tak szybko, jak (do współczynnika skalowania). Odnotowanie czasu działania algorytmu dla wielkości wejściowej , nieformalnie oznacza, że do pewnego współczynnika skalowania. $O(f(n))$ $n$ $K$ $K \, f(n)$ $f$ $T(n)$ $n$ $O(n)$ $T(n) \le f(n)$

Dolna granica

Czasami przydaje się mieć więcej informacji niż górna granica. jest odwrotnością : wyraża, że funkcja rośnie co najmniej tak szybko, jak inna. oznacza, że dla pewnego stałego , lub mówiąc nieformalnie, górę do pewnego współczynnika skalowania. $\Omega$ $O$ $T(n) = \Omega(g(n))$ $T(N) \ge K' g(n)$ $K'$ $T(n) \ge g(n)$

Kiedy czas działania algorytmu można precyzyjnie określić, łączy i : wyraża to, że znane jest tempo wzrostu funkcji, aż do współczynnika skalowania. oznacza, że dla niektórych stałych i . Mówiąc nieformalnie, do pewnego współczynnika skalowania. $\Theta$ $O$ $\Omega$ $T(n) = \Theta(h(n))$ $K h(n) \ge T(n) \ge K' h(n)$ $K$ $K'$ $T(n) \approx h(n)$

Dalsze uwagi

„Małe” i są używane znacznie rzadziej w analizie złożoności. Mała jest silniejsza niż duża ; gdzie oznacza wzrost, który nie jest szybszy, oznacza, że wzrost jest ściśle wolniejszy. I odwrotnie, wskazuje na zdecydowanie szybszy wzrost. $o$ $\omega$ $o$ $O$ $O$ $o$ $\omega$

Byłem nieco nieformalny w powyższej dyskusji. Wikipedia ma formalne definicje i bardziej matematyczne podejście.

Należy pamiętać, że użycie znaku równości w i tym podobne jest błędne. Ściśle mówiąc, jest zbiorem funkcji zmiennej i powinniśmy pisać . $T(n) = O(f(n))$ $O(f(n))$ $n$ $T \in O(f)$

Przykład: niektóre algorytmy sortowania

Ponieważ jest to raczej suche, dam przykład. Większość algorytmów sortowania ma kwadratowy najgorszy czas działania, tj. Dla danych wejściowych o rozmiarze czas działania algorytmu wynosi . Na przykład sortowanie selekcji ma czas działania , ponieważ wybranie tego elementu wymaga porównań , co daje łącznie porównania . W rzeczywistości liczba porównań wynosi zawsze dokładnie , co rośnie jako . Możemy więc dokładniej określić złożoność czasową sortowania selekcji: jest to . $n$ $O(n^2)$ $O(n^2)$ $k$ $n-k$ $n(n-1)/2$ $n(n-1)/2$ $n^2$ $\Theta(n^2)$

Teraz weź sortowanie korespondencji seryjnej . Sortowanie po scaleniu jest również kwadratowe ( ). To prawda, ale niezbyt precyzyjna. W rzeczywistości sortowanie korespondencji ma w najgorszym przypadku czas działania . Podobnie jak sortowanie selekcyjne, przepływ pracy sortowania scalającego jest zasadniczo niezależny od kształtu danych wejściowych, a jego czas działania wynosi zawsze do stałego mnożnika, tzn. Jest to . $O(n^2)$ $O(n \: \mathrm{lg}(n))$ $n \: \mathrm{lg}(n)$ $\Theta(n \: \mathrm{lg}(n))$

Następnie rozważ szybkie sortowanie . Quicksort jest bardziej złożony. Z pewnością jest to . Co więcej, najgorszy przypadek szybkiego sortowania jest kwadratowy: najgorszym przypadkiem jest . Jednak najlepszy przypadek szybkiego sortowania (gdy dane wejściowe są już posortowane) ma charakter liniowy: najlepsze, co możemy powiedzieć dla dolnej granicy szybkiego segmentu w ogóle, to . Nie powtórzę tutaj dowodu, ale średnia złożoność quicksort (średnia przejęta przez wszystkie możliwe kombinacje danych wejściowych) wynosi . $O(n^2)$ $\Theta(n^2)$ $\Omega(n)$ $\Theta(n \: \mathrm{lg}(n))$

Istnieją ogólne wyniki dotyczące złożoności algorytmów sortowania w typowych ustawieniach. Załóżmy, że algorytm sortowania może porównywać tylko dwa elementy jednocześnie, z wynikiem tak lub nie ( lub ). Jest zatem oczywiste, że czas działania dowolnego algorytmu sortującego to zawsze (gdzie jest liczbą elementów do posortowania), ponieważ algorytm musi przynajmniej raz porównać każdy element, aby wiedzieć, gdzie będzie pasował. Ta dolna granica może być spełniona, na przykład, jeśli dane wejściowe są już posortowane, a algorytm po prostu porównuje każdy element z następnym i utrzymuje je w porządku (to porównania ). Mniej oczywiste jest to, że maksymalny czas działania jest konieczny $x \le y$ $x > y$ $\Omega(n)$ $n$ $n-1$ $\Omega(n \: \mathrm{lg}(n))$ . Możliwe jest, że algorytm będzie czasem dokonywał mniej porównań, ale musi istnieć pewna stała tak że dla dowolnego rozmiaru wejściowego istnieje co najmniej jedno wejście, na którym algorytm daje więcej niż porównania. Ideą dowodu jest zbudowanie drzewa decyzyjnego algorytmu, tj. Śledzenie decyzji algorytmu na podstawie wyników każdego porównania. Ponieważ każde porównanie zwraca wynik „tak lub nie”, drzewo decyzyjne jest drzewem binarnym. Jestmożliwe permutacje danych wejściowych, a algorytm musi rozróżnić je wszystkie, więc wielkość drzewa decyzyjnego wynosi $K$ $n$ $K n \mathrm{lg}(n)$ $n!$ $n!$ . Ponieważ drzewo jest drzewem binarnym, do dopasowania wszystkich tych węzłów potrzeba . Głębokość to maksymalna liczba decyzji podejmowanych przez algorytm, więc uruchomienie algorytmu obejmuje co najmniej tyle porównań: maksymalny czas działania wynosi . $\Theta(\mathrm{lg}(n!)) = \Theta(n\:\mathrm{lg}(n))$ $\Omega(n \: \mathrm{lg}(n))$

¹ _{Lub inne zużycie zasobów, takie jak miejsce w pamięci. W tej odpowiedzi rozważam tylko czas działania.}

— Gilles
źródło

„Jednak najlepszy przypadek szybkiego sortowania (gdy dane wejściowe są już posortowane) ma charakter liniowy”, to jest najgorszy przypadek !!

— user5507

@ user5507: W rzeczywistości zależy to od strategii przestawnej. Jeśli pierwszy (lub ostatni) element zostanie wybrany jako pivot, masz rację; ale jeśli wybierzesz środkowy element lub medianę pierwszego, środkowego, ostatniego, to najlepiej posortowane dane wejściowe.

— chirlu

„Małe o i ω są używane znacznie rzadziej w analizie złożoności”. Nie dotyczy to analizy złożoności przestrzeni. W analizie złożoności czasu zwykle używasz o i ω, gdy liczysz określone operacje (porównania, poszukiwania dysku, brak pamięci podręcznej, co masz). Ale ponieważ zawsze możesz poczekać i kupić szybszy komputer, „czas na ścianę” zawsze „zależy od stałego czynnika”, więc big-O jest znacznie bardziej powszechny. W analizie przestrzeni często występują twarde dolne granice ze względu na teorię informacji, więc niezwykle często obserwujemy rozmiar zgłaszany jako „b (f) + o (f (n))”, gdzie f (n) jest dolną granicą.

— pseudonim

Chociaż myślę o tym: jeśli f (n) jest teoretyczną dolną granicą wielkości jakiejś struktury danych, to taką, która używa f (n) + O (1) (stały narzut), nazywa się „niejawną”, która używa f (n) + O (f (n)) (stały względny narzut) nazywa się „kompaktowym”, a ten, który używa f (n) + o (f (n)) (względny narzut staje się w końcu nieznaczny) nazywa się „zwięzłym „. Dobre warunki, aby wiedzieć, czy kiedykolwiek będziesz potrzebować pracować w tej przestrzeni.

— pseudonim

Zazwyczaj służy do określania górnych granic (oszacowanie z góry), podczas gdy służy do określania dolnych granic (oszacowanie z dołu), a jest używany, gdy pasują, w takim przypadku możesz użyć zamiast nich (zwykle), aby podać wynik. $O$ $\Omega$ $\Theta$ $\Theta$

— Kaveh
źródło

„Zazwyczaj”? Można je wykorzystać do czegoś innego?

— sick

@svick, tak, np. który nie jest instrukcją z górnej granicy. Przez górną granicę rozumiem coś takiego jak która wyraża górną granicę na .

P = D T i m e (n^{O (1)})

$\mathsf{P} = \mathsf{DTime}(n^{O(1)})$

f = O (g)

$f = O(g)$

f

$f$

— Kaveh

W rzeczywistości Kaveh, to jest górna granica zdania. Propoerowskie tłumaczenie „ ” brzmi „P jest zbiorem problemów, które można rozwiązać za pomocą AT MOST wielomianowej liczby operacji”. Jeśli nie miałeś na myśli „co najwyżej”, powinieneś napisać . (Oczywiście oba stwierdzenia są poprawne.)

P = D T i m e (n^{O (1)})

$P = DTime(n^{O(1)})$

P = D T i m e (n^{Θ (1)})

$P = DTime(n^{\Theta(1)})$

— JeffE

@JeffE, myślę o tym jako o równości między zestawami funkcji, ale masz rację, można również uznać to za górną granicę w bardziej ogólnym znaczeniu.

— Kaveh

@JeffE Właściwie , ponieważ ale .

P \neq D T I M E (n^{Θ (1)})

$\mathrm{P}\neq \mathrm{DTIME}(n^{\Theta(1)})$

D T I M E (Θ (n \log n)) \subset P

$\mathrm{DTIME}(\Theta(n\log n))\subset \mathrm{P}$

D T I M E (Θ (n \log n)) \cap D T I M E (n^{Θ (1)}) = \emptyset

$\mathrm{DTIME}(\Theta(n\log n))\cap\mathrm{DTIME}(n^{\Theta(1)})=\emptyset$

— David Richerby,