Jakie są cechy algorytmu złożoności czasowej

19

Czasami łatwo jest określić złożoność czasową algorytmu, dokładnie go badając. Algorytmy z dwiema zagnieżdżonymi pętlami są oczywiście . Algorytmy zbadania wszystkich możliwych kombinacji grup dwie wartości są oczywiście .N N 2 N.N2N2N

Nie wiem jednak, jak „rozpoznać” algorytm o złożoności . Przykładem jest rekurencyjna implementacja scalania. Jakie są wspólne cechy algorytmów scalesort lub innych algorytmów , które dałyby mi wskazówkę, gdybym je analizował?Θ(NlogN)Θ(NlogN)

Jestem pewien, że istnieje więcej niż jeden sposób złożoności algorytmu , więc każda odpowiedź jest doceniana. BTW Szukam ogólnych cech i wskazówek, a nie rygorystycznych dowodów.Θ(NlogN)

Barry Fruitman
źródło
6
O(logn) oznacza drzewo.
Pratik Deoghare
2
@PratikDeoghare: Niekoniecznie.
Raphael
3
@Raphael Miałem na myśli głównie! :)
Pratik Deoghare

Odpowiedzi:

17

Twój archetypiczny jest algorytmem „ dziel i rządź” , który dzieli (i rekombinuje) pracę w czasie liniowym i powraca nad kawałkami. Sortowanie z sortowaniem działa w ten sposób: poświęć czas O ( n ) na podzielenie danych wejściowych na dwa mniej więcej równe kawałki, rekurencyjnie posortuj każdy kawałek i poświęć Θ ( n ) czas na połączenie dwóch posortowanych połówek.Θ(nlogn)O(n)Θ(n)

Intuicyjnie, kontynuując ideę dziel i zwyciężaj, każdy etap podziału zajmuje w sumie czas liniowy, ponieważ wzrost liczby kawałków do podziału dokładnie odpowiada zmniejszeniu wielkości kawałków, ponieważ czas dzielenia jest liniowy. Całkowity czas pracy jest iloczynem całkowitego kosztu etapu podziału pomnożonego przez liczbę etapów podziału. Ponieważ wielkość kawałków jest za każdym razem zmniejszana o połowę, istnieją etapy podziału , więc całkowity czas pracy wynosi n log ( n ) . (Do stałej multiplikatywnej podstawa logarytmu nie ma znaczenia).log2(n)nlog(n)

Umieszczając go w równaniach (), jednym ze sposobów oszacowania czasu działania takiego algorytmu jest wyrażenie go rekurencyjnie: T ( n ) = 2 T ( n / 2 ) + Θ ( n ) . Oczywiste jest, że ten algorytm zajmuje więcej niż czas liniowy i możemy zobaczyć, o ile więcej, dzieląc przez n : T ( n )T(n)T(n)=2T(n/2)+Θ(n)n Gdynpodwaja się,T(n)/nwzrasta o stałą wartość:T(n)/nwzrasta logarytmicznie, lub innymi słowy,T(n)=Θ(nlogn).

T(n)n=T(n/2)n/2+Θ(1)
nT(n)/nT(n)/nT(n)=Θ(nlogn)

Jest to przykład bardziej ogólnego wzorca: twierdzenie główne . Dla każdego algorytm rekursywnego że dzieli dane wejściowe wielkości w a kawałki o rozmiarach n / b i ma czasową f ( n ) w celu wykonania podział i rekombinacji spełnia bieżącego czasu , T ( n ) = a T ( n / b ) + f ( n ) . Prowadzi to do zamkniętej formy, która zależy od wartości i B oraz kształtunan/bf(n)T(n)=aT(n/b)+f(n)ab . Jeśli = b i f ( n ) = Θ ( n ) , stany Master twierdzenie, że T ( n ) = Θ ( n log n ) .fa=bf(n)=Θ(n)T(n)=Θ(nlogn)

Gilles „SO- przestań być zły”
źródło
1
Podsumowując: algorytmy, które usuwają stały ułamek przestrzeni wyszukiwania na raz, będą wyświetlać terminy logarytmiczne. Inne czynniki zależą od tego, ile czasu zajmuje wykonanie odejścia.
Raphael
1
przykład: przeciętny średni przypadek O(nlogn)
od
11

Dwie inne kategorie algorytmów, które zajmują czasu:Θ(nlogn)

Algorytmy, w których każdy element jest przetwarzany kolejno, a przetwarzanie każdego elementu zajmuje czas logarytmiczny (np. HeapSort lub wiele algorytmów obliczeniowej geometrii płaszczyzny).

Algorytmy, w których czas wykonywania jest zdominowany przez etap wstępnego przetwarzania sortowania. (Na przykład, w algorytmie Kruskala dla minimalnego drzewa opinającego, możemy posortować krawędzie według wagi jako pierwszy krok).

Joe
źródło
Głosowano za pierwszy akapit. Drugi wydaje się zbędny, ponieważ algorytmy sortowania liniowo-rytmicznego, o których wiemy, albo dzielą i podbijają, albo stosy. Przykładem pierwszej kategorii jest wyszukiwanie obiektów w drzewie wyszukiwania binarnego (lub posortowanej tablicy) o rozmiarze n ; na bardziej abstrakcyjnym poziomie, który można jednak postrzegać jako dzielenie i podbijanie. nn
Raphael
@ Rafael Wiem, że sortowanie jest zbędne z podanymi kategoriami czasów pracy. Chodzi o to, że sortowanie bywa czasem „wąskim gardłem”, a algorytmy, w których na pierwszy rzut oka nie chodzi o sortowanie, mogą nadal mieć czas działania, ponieważ sortowanie jest wymagane.
Joe
9

Inna kategoria: Algorytmy, w których dane wyjściowe mają rozmiar , a zatem czas pracy Θ ( n log n ) jest liniowy w wielkości wyjściowej .Θ(nlogn)Θ(nlogn)

Chociaż szczegóły takich algorytmów często wykorzystują techniki dziel i zwyciężaj, niekoniecznie muszą. Czas działania zasadniczo wynika z zadanego pytania, dlatego uważam, że warto wspomnieć o nim osobno.

Pojawia się to w strukturach danych opartych na rozszerzonym drzewie wyszukiwania binarnego, w którym każdy węzeł przechowuje strukturę danych o rozmiarze liniowym do przeszukiwania liści w poddrzewie tego węzła. Takie struktury danych często pojawiają się podczas wyszukiwania zakresu geometrycznego i często są oparte na schemacie rozkładu . Zobacz ankietę Agarwal .

O(nlogn)O(logn)

Joe
źródło
θ(nlogn)
6

O(nlogn)kO(n)O(n)O(n)

Yuval Filmus
źródło
5

Są to zazwyczaj algorytmy odmiany „dziel i rządź”, w których koszt podziału i łączenia subolutions nie jest „zbyt duży”. Przejrzyj to FAQ, aby zobaczyć, jakie rodzaje nawrotów powodują takie zachowanie.

vonbrand
źródło
3

Zazwyczaj algorytmy dzielenia i zdobywania zapewniają złożoność O (N log N).

Brent Hronik
źródło
-1

O(nlogn)

for (i = 0; i < constant; i++){
    for(j = 0; j < n; j++){
        // Do some O(1) stuff on the input
    }
}

// Alternative Variant:
for (i = 0; i < constant; i++){
    for(j = n; j < constant; j++){
        // Do some O(1) stuff on the input
    }
}

O(n2)

Nie mogę podać konkretnego przykładu algorytmu wykorzystującego tę pętlę, ale często pojawia się podczas kodowania niestandardowych algorytmów.

Nicolas Miari
źródło
O(nlogn)Θ(n)Θ(1)Θ(|n|)n
O(nlogn)
ponadto pierwotne pytanie nie wymagało big-theta.
Nicolas Miari
1
O(nlogn)O(22n)O(almost anything else)Θ(nlogn)O(nlogn)
David Richerby
O(nlogn)O(nlogn)O(nlogn)O(nlogn)
Nicolas Miari