Biorąc pod uwagę ten pseudo-kod portu bąbelkowego:
FOR i := 0 TO arraylength(list) STEP 1
switched := false
FOR j := 0 TO arraylength(list)-(i+1) STEP 1
IF list[j] > list[j + 1] THEN
switch(list,j,j+1)
switched := true
ENDIF
NEXT
IF switched = false THEN
break
ENDIF
NEXT
Jakie podstawowe idee musiałbym pamiętać, aby ocenić średnią złożoność czasu? Obliczenia najgorszych i najlepszych przypadków zakończyłem już, ale utknąłem rozważając, jak ocenić średnią złożoność wewnętrznej pętli, aby utworzyć równanie.
Najgorsze równanie to:
w którym wewnętrzna sigma reprezentuje wewnętrzną pętlę, a zewnętrzna sigma reprezentuje zewnętrzną pętlę. Myślę, że muszę zmienić oba sigmy ze względu na klauzulę „jeśli-to-zepsuć”, która może wpływać na sigmę zewnętrzną, ale także z powodu klauzuli if w pętli wewnętrznej, która wpłynie na działania wykonywane podczas pętli (4 akcje + 1 porównanie, jeśli to prawda, w przeciwnym razie tylko 1 porównanie).
W celu wyjaśnienia terminu średni czas: ten algorytm sortowania będzie wymagał innego czasu na różnych listach (o tej samej długości), ponieważ algorytm może wymagać więcej lub mniej kroków przez pętle / w pętli, dopóki lista nie będzie całkowicie uporządkowana. Staram się znaleźć matematyczny (niestatystyczny sposób) szacowanie średniej potrzebnych rund.
W tym celu oczekuję, że każde zamówienie będzie miało taką samą możliwość.
Odpowiedzi:
W przypadku list o długości średnia oznacza zwykle, że musisz zacząć od jednolitego rozkładu na wszystkie n ! permutacje [ 1 , .., n ]: to będą wszystkie listy, które musisz wziąć pod uwagę.n n ! 1 n
Twoja średnia złożoność byłaby wówczas sumą liczby kroków dla wszystkich list podzieloną przez .n !
Następnie wykonujesz matematykę: dla każdego znajdź liczbę list z tą konkretną maksymalną odległością, a następnie oczekiwana wartość wynosi:c d dre dore re
I to są podstawowe myśli bez najtrudniejszej części znalezienia . Być może istnieje jednak prostsze rozwiązanie.dore
EDYCJA: dodano „oczekiwany”
źródło
Przypomnij sobie, że para (odpowiednio. ) jest odwrócona, jeśli i .( i , j ) i < j A [ i ] > A [ j ]( A [ i ] , A [ j ] ) ( i , j ) ja < j A [ i ] > A [ j ]
Zakładając, że algorytm wykonuje jedną zamianę dla każdej inwersji, czas działania algorytmu będzie zależał od liczby inwersji.
Obliczanie oczekiwanej liczby inwersji w jednolitej przypadkowej permutacji jest łatwe:
Niech być permutacją i pozwolić jest odwrotna . Na przykład, jeśli to .R ( P ) P P = 2 , 1 , 3 , 4 R ( P ) = 4 , 3 , 1 , 2P. R ( P) P. P.= 2 , 1 , 3 , 4 R ( P) = 4 , 3 , 1 , 2
Dla każdej pary wskaźników występuje odwrócenie w dokładnie jednym z lub .P R ( P )( i , j ) P. R ( P)
Ponieważ całkowita liczba par wynosi , a całkowita liczba i każda para jest odwrócona dokładnie w połowie permutacji, zakładając, że wszystkie permutacje są jednakowo prawdopodobne, oczekiwana liczba inwersji wynosi:n ( n - 1 ) / 2
źródło
Liczba zamian <Liczba iteracji (zarówno w zoptymalizowanym, jak i prostym scenariuszu bąbelkowym)
Liczba inwersji = liczba zamian.
Dlatego liczba iteracji>n ( n - 1 )4
Zatem średnia złożoność przypadków wynosi . Ale ponieważ średnia liczba przypadków nie może przekroczyć najgorszego przypadku, otrzymujemy, że jest to ,O ( n 2 )ω ( n2)) O ( n2))
To daje nam: Średni czas =θ ( n2))
(Złożoność czasu = liczba iteracji liczba iteracji> liczba swapów)
źródło
w tym dokumencie średnia złożoność czasowa sortowania bąbelkowego osiągnęła O (nlog (n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf
źródło