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:

\sum_{ja = 0}^{n} (\sum_{jot = 0}^{n - (ja + 1)} O (1) + O (1)) = O (\frac{n^{2)}}{2)} + \frac{n}{2)}) = O (n^{2)})

$\sum_{i=0}^n \left(\sum_{j=0}^{n -(i+1)}O(1) + O(1)\right) = O(\frac{n^2}{2} + \frac{n}{2}) = O(n^2)$

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ż wynosi

n^{2}

$n^2$

— 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,

9

W przypadku list o długości średnia oznacza zwykle, że musisz zacząć od jednolitego rozkładu na wszystkie permutacje [ , .., ]: 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!$

$(x_i)_i$ $nd$ $d$ $x_i$ $i$ $\max_i(\max(1,i-x_i))$

Następnie wykonujesz matematykę: dla każdego znajdź liczbę list z tą konkretną maksymalną odległością, a następnie oczekiwana wartość wynosi: $d$ $c_d$ $d$

\frac{1}{n!} \sum_{re = 0}^{n} re {do}_{re}

$\frac1{n!}\ \sum_{d=0}^n{\ dc_d}$

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

EDYCJA: dodano „oczekiwany”

— jmad
źródło

Jeśli weźmiesz pod uwagę rozkład normalny, czy istnieje sposób na przybliżenie ?

c_{d}

$c_d$

— 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 .

c_{d} \geq (n + 1 - d) (d - 1)!

$c_d≥(n+1-d)(d-1)!$

2

$2$

d

$d$

1

$1$

n ²

$n²$

— jmad

19

Przypomnij sobie, że para (odpowiednio. ) jest odwrócona, jeśli i . $(A[i], A[j])$ $(i,j)$ $i < 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 . $P$ $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 . $(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$

\frac{n (n - 1)}{4}

$\frac{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> $\frac{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 , $\omega(n^2)$ $O(n^2)$

To daje nam: Średni czas = $\theta(n^2)$

(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 .

n^{2} / 2

$n^2/2$

— Yuval Filmus