Dlaczego jest połączony O (log n)?

Mergesort jest algorytmem dzielenia i zdobywania i ma wartość O (log n), ponieważ dane wejściowe są wielokrotnie zmniejszane o połowę. Ale czy nie powinno to być O (n), ponieważ mimo że dane wejściowe są zmniejszone o połowę w każdej pętli, każdy element wejściowy musi być iterowany, aby wykonać zamianę w każdej z połówek tablicy? Moim zdaniem jest to zasadniczo asymptotycznie O (n). Jeśli to możliwe, podaj przykłady i wyjaśnij, jak poprawnie policzyć operacje! Jeszcze niczego nie kodowałem, ale szukałem algorytmów online. Dołączyłem również gif, z którego wikipedia korzysta, aby wizualnie pokazać, jak działa scalanie.

To O (n * log (n)), a nie O (log (n)). Jak dokładnie się domyślasz, całe dane wejściowe muszą być iterowane, a to musi się zdarzyć O (log (n)) razy (wejście może być tylko o połowę O (log (n)) razy). n pozycji iterowany log (n) razy daje O (n log (n)).

Udowodniono, że żaden rodzaj porównania nie może działać szybciej. Tylko sortowania, które opierają się na specjalnej właściwości danych wejściowych, takie jak sortowanie radix, mogą pokonać tę złożoność. Stałe czynniki łączenia nie są zazwyczaj świetne, więc algorytmy o gorszej złożoności często zajmują mniej czasu.

Złożoność sortowania przez scalenie to O (nlogn) i NOT O (logn).

Scal sortowanie to algorytm dzielenia i zdobywania. Pomyśl o tym w kategoriach 3 kroków -

1. Krok dzielenia oblicza punkt środkowy każdej z tablic podrzędnych. Każdy z tych kroków zajmuje tylko O ​​(1).
2. Etap podboju rekurencyjnie sortuje dwie podgrupy n / 2 (nawet dla n) elementów.
3. Krok scalania scala n elementów, co zajmuje czas O (n).

Teraz, dla kroków 1 i 3, tj. Między O (1) a O (n), O (n) jest wyższe. Rozważmy, że kroki 1 i 3 zajmują w sumie czas O (n). Powiedzmy, że jest cn dla jakiegoś stałego c.

Ile razy te kroki są wykonywane?

W tym celu spójrz na poniższe drzewo - dla każdego poziomu od góry do dołu wywołania metody poziomu 2 łączą się w 2 pod-macierzach o długości n / 2 każdy. Złożoność tutaj wynosi 2 * (cn / 2) = cn Metoda wywołania na poziomie 3 na 4 pod-macierzach o długości n / 4 każda. Złożoność tutaj wynosi 4 * (cn / 4) = cn i tak dalej ...

Wysokość tego drzewa wynosi (logn + 1) dla danego n. Zatem ogólna złożoność wynosi (logn + 1) * (cn). To jest O (nlogn) dla algorytmu sortowania po scaleniu.

Zdjęcia: Khan Academy

Scal sortowanie jest algorytmem rekurencyjnym, a złożoność czasowa może być wyrażona jako następująca relacja powtarzalności.

T (n) = 2 T (n / 2) + ɵ (n)

Powyższą rekurencję można rozwiązać za pomocą metody drzewa rekurencyjnego lub metody głównej. Wypada w przypadku II Metody Głównej, a rozwiązaniem nawrotu jest ɵ (n log n).

Złożoność czasowa sortowania scalonego wynosi ɵ (nLogn) we wszystkich 3 przypadkach (najgorszy, średni i najlepszy), ponieważ sortowanie scalone zawsze dzieli tablicę na dwie połowy i zajmuje czas liniowy na scalenie dwóch połówek.

Dzieli tablicę wejściową na dwie połowy, nazywa się dwiema połówkami, a następnie łączy dwie posortowane połowy. Funkcja scal () służy do łączenia dwóch połówek. Scalanie (arr, l, m, r) jest kluczowym procesem, który zakłada, że ​​arr [l..m] i arr [m + 1..r] są sortowane i łączy dwa posortowane pod-tablice w jedno. Zobacz szczegóły implementacji C.

MergeSort(arr[], l,  r)
If r > l
     1. Find the middle point to divide the array into two halves:  
             middle m = (l+r)/2
     2. Call mergeSort for first half:   
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)

Jeśli przyjrzymy się bliżej diagramowi, zobaczymy, że tablica jest rekurencyjnie dzielona na dwie połowy, aż rozmiar osiągnie 1. Gdy rozmiar osiągnie 1, procesy scalania zaczynają działać i zaczynają scalać tablice z powrotem, aż cała tablica zostanie scalone.

Algorytmy sortowania na podstawie porównania mają dolną granicę 𝞨(n*log(n)), co oznacza, że ​​nie można mieć algorytmu sortowania na podstawie porównania o O(log(n))złożoności czasowej.

Nawiasem mówiąc, sortowanie według scalania jest O(n*log(n)). Pomyśl o tym w ten sposób.

[ a1,a2,         a3,a4,         a5,a6,          a7,a8     .... an-3,an-2,     an-1, an ] 
   \ /            \  /           \ /             \  /            \  /            \  /    
    a1'            a3'            a5'             a7'            an-3'           an-1'    
      \            /                \             /                 \             /
            a1''                          a5''                       an-3''
             \                             /                         /
                          a1'''                                     /
                           \
                                              a1''''

To wygląda na odwrócone drzewo binarne.

Niech rozmiar wejściowy będzie n.

Każdy a_nreprezentuje listę elementów. Pierwsza linia a_nma tylko jeden element.

Na każdym poziomie średnia suma kosztu scalenia wynosi n(istnieją przypadki narożne, których koszt jest niższy [1]). A wysokość drzewa to log_2(n).

Zatem złożoność czasowa sortowania scalającego jest O(n*log_2(n)).

[1] w przypadku sortowania na liście, która jest już posortowana, co nazywa się najlepszym przypadkiem. koszt obniżony do n/2 + n/4 + n/8 + .... + 1 = 2^log_2(n) -1 ~ O(n). (załóżmy, że długość nto potęga dwóch)

Sortowanie jest problemem NP-Complete w informatyce (problem niejednorodny). Oznacza to, że jeśli nie zostanie to udowodnione matematycznie, nie można zejść poniżej O (n log n) podczas sortowania listy elementów.

Sprawdź ten artykuł w Wikipedii ( https://en.wikipedia.org/wiki/P_versus_NP_problem )

Zasadniczo jak dotąd nikomu nie udało się udowodnić, że (P == NP), a jeśli to zrobisz, najpierw zostaniesz milionerem, a następnie rozpoczniesz III wojnę światową ze względu na fakt, że będziesz w stanie złamać wszystkie użyte mechanizmy bezpieczeństwa klucza publicznego / prywatnego wszędzie dzisiaj :)