Czy ktoś jest w stanie podać "zwykły angielski" intuicyjne, ale formalne wyjaśnienie, co powoduje, że QuickSort n log n? Z mojego rozumowania musi on przejść przez n pozycji, i robi to log n razy ... Nie jestem pewien, jak umieścić to w słowach, dlaczego robi to log n razy.Intuicyjne wyjaśnienie, dlaczego QuickSort to n log n?
Każda operacja partycjonowania wymaga operacji O (n) (jedno przejście w tablicy). Średnio, każde partycjonowanie dzieli tablicę na dwie części (sumujące się do operacji log n). W sumie mamy operacje O (n * log n).
tj. w typowych operacjach partycjonowania log n, a każda partycja wykonuje operacje O (n).
Część log n pochodzi z faktu, że jest to (co najmniej idealnie) przełamanie wejścia w połowie w każdej iteracji. Zaczynając od N pozycji, a rozbijanie ich o połowę za każdym razem oznacza, że przechodzisz do 1 pozycji po logach (N), w którym to momencie nie możesz dalej go dzielić. Na przykład, zaczynając od, powiedzmy, 128 elementów, dzielisz się na grupy składające się z 64, 32, 16, 8, 4, 2, 1 elementów - 7 iteracji (i log (128) = 7).
Każda z tych iteracji przeszukuje całą tablicę, aby ją podzielić, więc kończy się operacjami O (log N), z których każda ma złożoność O (n), dla ogólnej złożoności O (n log n).
Aby być technicznie poprawnym, Big-O jest O (N). Wynika to z faktu, że wystarczająco zły wybór elementu partycji może podzielić tablicę na jeden element z jednej strony, a całą resztę tablicy na drugą. Jeśli dzieje się to przy każdej iteracji, to wymaga N iteracji, aby podzielić ją na części po jednym elemencie, więc otrzymasz operacje N, każda o złożoności O (N), dla O (N * N) ogólnie.
W prawdziwej implementacji zwykle zatrzymuje się przed tym, ale to jest najdalej można przejść.
Cóż, nie zawsze jest to n (log n). Jest to czas wykonania, gdy wybrany jest mniej więcej pośrodku. W najgorszym wypadku, jeśli wybierzesz najmniejszy lub największy element jako oś obrotu, wówczas będzie to O (n^2).
Aby wizualizować "n log n", można założyć, że oś obrotu jest elementem najbliższym średniej wszystkich elementów w tablicy do posortowania. To podzieliłoby tablicę na 2 części o mniej więcej tej samej długości. W obu przypadkach stosuje się procedurę quicksort.
Tak jak w każdym kroku, w którym zmniejszono o połowę długość tablicy, zrobisz to dla log n (podstawa 2) razy, aż osiągniesz długość = 1, czyli posortowaną tablicę 1 elementu.
Masz rację, ale nie mieszaj średniej i mediany. Mediana pozwala dzielić na dwie części o tej samej długości (+ -1). – kvetis
W rzeczywistości trzeba znaleźć położenie wszystkich elementów N (przestawny), ale maksymalna liczba porównań to logN dla każdego elementu (pierwszy to N, drugi węzeł N/2,3rd N/4. .wartość przestawna jest medianą)
Dziękuję za to. Przyjęta tu odpowiedź jedynie skorygowała to, co OP (i I) już znali (n operacji wykonano log n razy), ale pominęło tylko ważną część: dlaczego jest zrobione log n razy? Ta odpowiedź jest miłym i prostym wyjaśnieniem, skąd pochodzi log. –
jest bardzo jasne, dzięki odpowiedź. – huseyin
to jest najlepsze wytłumaczenie – huseyin