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

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^2$$N$$2^N$

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ł?$\Theta(N \log N)$$\Theta(N \log N)$

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.$\Theta(N \log N)$

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.$\Theta(n \log n)$$O(n)$$\Theta(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).$\log_2(n)$$n \cdot \log(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) = 2 T(n/2) + \Theta(n)$$n$ Gdynpodwaja się,T(n)/nwzrasta o stałą wartość:T(n)/nwzrasta logarytmicznie, lub innymi słowy,T(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łtu$n$$a$$n/b$$f(n)$$T(n) = a \cdot T(n/b) + f(n)$$a$$b$ . Jeśli = b i f ( n ) = Θ ( n ) , stany Master twierdzenie, że T ( n ) = Θ ( n log n ) .$f$$a = b$$f(n) = \Theta(n)$$T(n) = \Theta(n \log n)$

Dwie inne kategorie algorytmów, które zajmują czasu:$\Theta(n \log n)$

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).

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 .$\Theta(n \log n)$$\Theta(n \log n)$

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(n \log n)$$O(\log n)$

$O(n\log n)$$k$$O(n)$$O(n)$$O(n)$

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.

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

$O(n \log n)$

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(n^2)$

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