Ocena średniej złożoności czasowej danego algorytmu bąbelkowego.

11

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:

ja=0n(jot=0n-(ja+1)O(1)+O(1))=O(n2)2)+n2))=O(n2))

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ść.

Sim
źródło
6
najpierw musisz zdefiniować, co oznacza średnia. Ponieważ algorytm jest deterministyczny, musiałbyś przyjąć pewien rozkład między wejściami.
Suresh
@Sim Czy możesz pokazać, w jaki sposób obliczyłeś złożoność najgorszego przypadku? Następnie możemy dowiedzieć się, co rozumiesz przez średnią złożoność w twoim przypadku.
0x0
Mam na myśli średni czas jako najbardziej prawdopodobny potrzebny czas (lub innymi słowy „czystą” matematyczną wersję: średniej z wszystkich zaobserwowanych czasów podczas analizy statystycznej). Na przykład quicksort ma średnią wartość nlogn, chociaż najgorszym przypadkiem jest n ^ 2.
Sim
1
@Sim W przypadku sortowania bąbelkowego średnia wielkość liter = najgorszy czas złożoności przypadku, co oznacza, że ​​średni czas złożoności przypadku również wynosin2)
0x0
3
Jest różnica. quicksort jest uśredniany „przed wyborem rzutów monetą przy wyborze osi obrotu”, co nie ma nic wspólnego z danymi. Podczas gdy implikujesz, że chcesz uśrednić „na wszystkich wejściach”, co zakłada (na przykład), że oczekujesz, że każde uporządkowanie danych wejściowych nastąpi z takim samym prawdopodobieństwem. to rozsądne, ale należy to wyraźnie zaznaczyć.
Suresh,

Odpowiedzi:

9

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ę.nn!1n

Twoja średnia złożoność byłaby wówczas sumą liczby kroków dla wszystkich list podzieloną przez .n!

(xja)janrerexjajamaxja(max(1,ja-xja))

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 dredorere

1n! re=0n redore

I to są podstawowe myśli bez najtrudniejszej części znalezienia . Być może istnieje jednak prostsze rozwiązanie.dore

EDYCJA: dodano „oczekiwany”

jmad
źródło
Jeśli weźmiesz pod uwagę rozkład normalny, czy istnieje sposób na przybliżenie ? dore
Sim
Możesz powiedziećponieważ możesz mieszać w dowolnym miejscu wszystkie kombinacje [ , .., ] i dołączać na końcu, ale to jest małe, aby udowodnić średnio . 2 d 1 n ²cd(n+1d)(d1)!2d1n²
jmad
19

Przypomnij sobie, że para (odpowiednio. ) jest odwrócona, jeśli i .( i , j ) i < j A [ i ] > A [ j ](ZA[ja],ZA[jot])(ja,jot)ja<jotZA[ja]>ZA[jot]

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),4R(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 )(ja,jot)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)

n(n-1)4
Joe
źródło
ocenia to liczbę inwersji. ale co z ilością porównań, które zależą od czasu, w którym pojawia się klauzula wyłączająca
Sim
Otrzymujesz jedno porównanie poprzez zamianę, a co najważniejsze, jedna zamiana może zmniejszyć liczbę inwersji maksymalnie o jedną.
jmad
nie każde porównanie powoduje zamianę, jeśli klauzula if jest fałszem, nie jest przeprowadzana inwersja.
Sim
@rgrig Jeśli podasz kontrprzykład, poprawię moją odpowiedź.
Joe
@Joe: Usunąłem swój komentarz. To było złe
rgrig
2

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)

kushj
źródło
0

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

użytkownik84630
źródło
1
To nieprawda. Udowadniają, że Knuth wykazał, że oczekiwana liczba porównań wynosi w przybliżeniu . n2)/2)
Yuval Filmus