Cześć mam pytanie jak złozoność obliczeniowa QuickSort zależy od wybory pivota czyli elementu dzielącego X i od struktury sortowanego ciągu ?
- Rejestracja:prawie 7 lat
- Ostatnio:prawie 2 lata
- Postów:232
- Rejestracja:prawie 8 lat
- Ostatnio:5 miesięcy
- Postów:231
1
Wybór pivota w sortowaniu szybkim mówi o tym jaki będzie wysokość stosu wywołań. Jeśli ustawisz element osiowy na pierwszy element tablicy, którą chcesz posortować to stos wywołań będzie miał złożoność obliczeniową O(n) w najgorszym przypadku, jeśli elementem osiowym będzie element o indexie środkowym sortowaniem tablicy to wysokość stosu wywołań będzie miała złożoność obliczeniową O(log(n)). Przy czym samo sortowanie zawsze będzie posiadało złożoność obliczeniową O(n) więc sprawa wygląda następująco:
- najgorszy przypadek przy piwocie arr[0] -->
O(n^2) - najgorszy przypadek przy piwocie, który jest za każdym razem indexem środkowym tablicy sortowanej -->
O(nlog(n))
Tutaj różnicę robi właśnie ten poziom stosu wywołań, który może się zmieniać w zależności od doboru elementu osiowego -> możesz dzielić cały czas tablice na pół przy ich sortowaniu co daje właśnie O(log(n)) a możesz mieć element osiowy jako skrajny element tablicy wówczas poziom stosu wywołań rośnie liniowo, bo piwot jedynie inkrementujesz a zatem tworzy to złożoność O(n).
- Rejestracja:prawie 8 lat
- Ostatnio:5 miesięcy
- Postów:231
0
No właśnie odwrotnie. Polecaną techniką jest wybieranie albo losowego albo środkowego indeksu sortowanej tablicy, żeby osiągnąć złożoność O(log(n)) poziomu wywołań stosu. Przecież O(n) to złożoność obliczeniowa, która rośnie liniowo, a więc jest to przypadek dość zły pod kątem ilości operacji do wykonania - oczywiście różnica jest zauważalny przy większych tablicach typu 4 miliardy elementów na przykład.
edytowany 1x, ostatnio: Shizzer
- Rejestracja:prawie 7 lat
- Ostatnio:prawie 2 lata
- Postów:232
0
Dobra dzięki za odpowiedź a mam jeszcze jedno pytanko:
aby obliczyć czas wykonania obliczeń dla QuickSorta dla n=10 w którym uporządkowanie początkowe jest :
niemalejące czyli sortowane ma być od najmniejszej do największej liczby
nierosnące czyli sortowanie ma być od największej do najmniejszej liczby
a co oznacza uporządkowanie początkowe losowe ?
edytowany 3x, ostatnio: Cisi204
- Rejestracja:prawie 8 lat
- Ostatnio:5 miesięcy
- Postów:231
0
"Najprostsza, "naiwna" metoda podziału – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporządkowanych daje katastrofalną złożoność O(n^2)." Oczywiście chodzi tutaj o (poziom wywołań stosu * ilośc operacji potrzebnych do sortowania)
edytowany 1x, ostatnio: Shizzer
- Rejestracja:prawie 7 lat
- Ostatnio:prawie 2 lata
- Postów:232
0
A masz możne program w c++ przyrównujący procesy wszystkich algorytmów sortowania , mam na myśli taki program w którym podajesz liczbę elementów n a , a po wykonaniu wszystkich porównań algorytm taki wyrzuca ci czas wykonania kodu
edytowany 1x, ostatnio: Cisi204
- Rejestracja:około 8 lat
- Ostatnio:minuta
- Postów:4915
1
Żeby zminimalizować szanse na złożonośż kwadratową, standartowo stosuje się "median-of-3" - czyli piwotem jest mediana pierwszego, ostatniego i środkowego elementu (C++ STL). Biblioteki standartowe mają swoje sposoby na optymalizacje sortwania:
edytowany 2x, ostatnio: lion137