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.
algorithms
big-o
wytrwałość
źródło
źródło
Odpowiedzi:
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.
źródło
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 -
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
źródło
Scal sortowanie jest algorytmem rekurencyjnym, a złożoność czasowa może być wyrażona jako następująca relacja powtarzalności.
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.
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.
źródło
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 oO(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.To wygląda na odwrócone drzewo binarne.
Niech rozmiar wejściowy będzie
n
.Każdy
a_n
reprezentuje listę elementów. Pierwsza liniaa_n
ma 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 tolog_2(n)
.Zatem złożoność czasowa sortowania scalającego jest
O(n*log_2(n))
.źródło
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 :)
źródło