Jak wygląda ten algorytm sortowania Θ (n³), a nie Θ (n²), w najgorszym przypadku?

52

Właśnie zaczynałem kurs na temat struktur danych i algorytmów, a mój asystent nauczycielski dał nam następujący pseudo-kod do sortowania tablicy liczb całkowitych:

void F3() {
    for (int i = 1; i < n; i++) {
        if (A[i-1] > A[i]) {
            swap(i-1, i)
            i = 0
        }
    }
}

To może nie być jasne, ale tutaj jest rozmiarem tablicy , którą próbujemy posortować. $n$ A

W każdym razie asystent nauczycielski wyjaśnił klasie, że ten algorytm jest w czasie (jak sądzę, w najgorszym przypadku), ale bez względu na to, ile razy go przeglądam z odwróconą tablicą, wydaje mi się, że powinno to być a nie . $\Theta(n^3)$ $\Theta(n^2)$ $\Theta(n^3)$

Czy ktoś mógłby mi wyjaśnić, dlaczego jest to $Θ(n^3)$ a nie $Θ(n^2)$ ?

— Anthony Rossello
źródło

Możesz być zainteresowany ustrukturyzowanym podejściem do analizy ; spróbuj sam znaleźć dowód!

— Raphael

Wystarczy go wdrożyć i zmierzyć, aby się przekonać. Tablica z 10 000 elementów w odwrotnej kolejności powinna zająć wiele minut, a tablica z 20 000 elementów w odwrotnej kolejności powinna zająć około osiem razy dłużej.

— gnasher729

@ gnasher729 Nie mylisz się, ale moje rozwiązanie jest inne: jeśli spróbujesz udowodnić swoją granicę , niezmiennie zawiedziesz, co powie ci, że coś jest nie tak. (Oczywiście można zrobić jedno i drugie. Rysowanie / dopasowywanie jest zdecydowanie szybsze w celu odrzucenia hipotezy, ale mniej niezawodne . Tak długo, jak robisz coś dla formalnej / ustrukturyzowanej analizy, nie szkodzi. Poleganie na działkach jest tam, gdzie zaczynają się kłopoty.)

O (n^{2})

$O(n^2)$

— Raphael

1

z powodu i = 0oświadczenia

— njzk2

60

Ten algorytm można ponownie zapisać w ten sposób

Skanuj, Aaż znajdziesz odwrócenie .
Jeśli znajdziesz, zamień i zacznij od nowa.
Jeśli nie ma, zakończ.

Teraz może być co najwyżej inwersje i potrzebujesz skanowania w czasie liniowym, aby je znaleźć - więc najgorszym przypadkiem jest . Piękny przykład dydaktyczny, który potęguje podejście polegające na dopasowywaniu wzorców, któremu wielu ulega! $\binom{n}{2} \in \Theta(n^2)$ $\Theta(n^3)$

Nota bene: Trzeba być trochę ostrożnym: niektóre inwersje pojawiają się wcześnie, niektóre późno, więc per se nie jest trywialne, że koszty sumują się zgodnie z deklaracją (dla dolnej granicy). Musisz także zauważyć, że swapy nigdy nie wprowadzają nowych inwersji. Bardziej szczegółowa analiza przypadku z odwrotnie posortowaną tablicą da wtedy coś w rodzaju kwadratu z wzoru Gaussa.

Jak trafnie komentuje @ gnasher729, łatwo zauważyć, że najgorszym przypadkiem jest , analizując czas działania podczas sortowania danych wejściowych (chociaż to wejście prawdopodobnie nie jest najgorszym przypadkiem). $\Omega(n^3)$ $[1, 2, \dots, n, 2n, 2n-1, \dots, n+1]$

Uważaj: nie zakładaj, że odwrotnie posortowana tablica będzie koniecznie najgorszym wprowadzeniem dla wszystkich algorytmów sortowania. To zależy od algorytmu. Istnieje kilka algorytmów sortowania, w których odwrotnie posortowana tablica nie jest najgorszym przypadkiem, a nawet może być bliska najlepszym przypadkom.

— Raphael
źródło

14

Jeśli weźmiesz tablicę, w której pierwsza połowa składa się z liczb od 1 do n / 2 w porządku rosnącym, a druga połowa to n do n / 2 + 1 w odwrotnej kolejności, to oczywiste, że potrzebujesz co najmniej n / 2 kroki, aby znaleźć każdą inwersję, a będzie ich około (n / 2) ^ 2/2. I najprawdopodobniej nie jest to najgorszy przypadek.

— gnasher729

@AnthonyRossello Jest to standardowy wynik (w kombinatoryce permutacji). Krótko mówiąc, policz liczbę inwersji w tablicy posortowanej odwrotnie (czy to oczywiste, że to najgorszy przypadek?); to suma Gaussa.

— Raphael

Trzeba pamiętać, że bez względu na wszystko, częściowe sumy są zawsze , to tylko współczynnik, który szybko spada: (zwróć uwagę na dość duży współczynnik ). Problem w tym, że nie dba o współczynniki.

Θ (n^{α})

$\Theta(n^\alpha)$

Θ (n^{α + 1})

$\Theta(n^{\alpha+1})$

\sum_{k = 0}^{n} k^{α} \sim \frac{1}{α + 1} n^{α + 1}

$\sum_{k=0}^n k^\alpha \sim \frac{1}{\alpha+1} n^{\alpha+1}$

\frac{1}{α + 1}

$\frac{1}{\alpha+1}$

Θ

$\Theta$

— yo „

2

@yo 'A to odnosi się do odpowiedzi (lub pytania) w jaki sposób?

— Raphael

7

Alternatywnym sposobem myślenia o tym jest, jaka jest maksymalna wartość iprzed zresetowaniem. Jak się okazuje, łatwiej jest zrozumieć, w jaki sposób poprzednia kolejność sortowania Awpływa na czas działania algorytmu.

W szczególności zauważ, że kiedy iustawia się nową maksymalną wartość, nazwijmy ją N, tablica [A[0], ..., A[N-1]]jest sortowana w porządku rosnącym.

Co się stanie, gdy dodamy element A[N]do miksu?

Matematyka:

Powiedzmy, że pasuje do pozycji . Następnie potrzebujemy iteracji pętli (które oznaczę ), aby przenieść ją do położenia , aby przenieść ją do miejsca i ogólnie: $p_N$ $N$ $\text{steps}$ $N-1$ $N + (N-1)$ $N-2$

{steps}_{N} (p_{N}) = N + (N - 1) + (N - 2) + \dots + (p_{N} + 1) = \frac{1}{2} (N (N + 1) - p_{N} (p_{N} + 1))

$\text{steps}_N(p_N) = N + (N-1) + (N-2) + \dots + (p_N+1) = \tfrac{1}{2}(N(N+1) - p_N(p_N+1))$

W przypadku losowo posortowanej tablicy przyjmuje rozkład równomierny na dla każdego , z: $p_N$ $\{0, 1,\dots, N\}$ $N$

E ({steps}_{N} (p_{N})) = \sum_{a = 1}^{N} P (p_{N} = a) {steps}_{N} (a) = \sum_{a = 1}^{N} \frac{1}{N} \frac{1}{2} (N (N + 1) - a (a + 1)) = \frac{1}{2} (N (N + 1) - \frac{1}{3} (N + 1) (N + 2)) = \frac{1}{3} (N^{2} - 1) = Θ (N^{2})

$\mathbb{E}(\text{steps}_N(p_N)) = \sum_{a=1}^{N} \mathbb{P}(p_N = a)\text{steps}_N(a) = \sum_{a=1}^{N}\tfrac{1}{N}\tfrac{1}{2}(N(N+1) - a(a+1)) = \tfrac{1}{2} ( N(N+1) - \tfrac{1}{3}(N+1)(N+2)) = \tfrac{1}{3} (N^2-1) = \Theta(N^2)$

suma może być pokazana za pomocą wzoru Faulhabera lub łącza Wolfram Alpha na dole.

Dla odwrotnie posortowanej tablicy, dla wszystkich , i otrzymujemy: $p_N=0$ $N$

{steps}_{N} (p_{N}) = \frac{1}{2} N (N + 1)

$\text{steps}_N(p_N) = \tfrac{1}{2}N(N+1)$

dokładnie, biorąc ściśle dłużej niż jakakolwiek inna wartość . $p_N$

W przypadku już posortowanej tablicy i , przy czym terminy niższego rzędu stają się odpowiednie. $p_N = N$ $\text{steps}_N(p_N) = 0$

Czas całkowity:

Aby uzyskać całkowity czas, możemy podsumować kroki nad wszystkimi . (Gdybyśmy byli bardzo ostrożni, podsumowalibyśmy swapy, a także iteracje pętli i zadbali o warunki początkowe i końcowe, ale dość łatwo jest zauważyć, że w większości przypadków nie przyczyniają się do złożoności) . $N$

I znowu, używając liniowości oczekiwań i Formuły Faulhabera:

Expected Total Steps = E (\sum_{N = 1}^{n} {steps}_{N} (p_{N})) = \sum_{N = 1}^{n} E ({steps}_{N} (p_{N})) = Θ (n^{3})

$\text{Expected Total Steps} = \mathbb{E}(\sum_{N=1}^n \text{steps}_N(p_N)) = \sum_{N=1}^n \mathbb{E}(\text{steps}_N(p_N)) = \Theta(n^3)$

Oczywiście, jeśli z jakiegoś powodu nie jest (np. Rozkład tablic, na który patrzymy, jest już bardzo bliski sortowania), to nie zawsze musi to być sortowane niech tak będzie. Ale aby to osiągnąć, potrzeba bardzo specyficznych dystrybucji na ! $\text{steps}_N(p_N)$ $\Theta(N^2)$ $p_N$

Odpowiednia lektura:

https://www.wolframalpha.com/input/?i=sum+a(a%2B1)+from+a%3D1+to+a%3DN
https://en.wikipedia.org/wiki/Faulhaber%27s_formula - Formuła Faulhabera

— David E.
źródło

@ Rafael - dziękuję za sugerowane ulepszenia, dodałem trochę więcej szczegółów. Cóż, zmiennymi losowymi są (z , zestaw uporządkowania ), więc technicznie oczekiwania są spełnione względem

p_{i}

$p_i$

Ω

$\Omega$ A

Ω

$\Omega$

— David E

Różne ; Miałem na myśli Landau.

Ω

$\Omega$

— Raphael

3

Zrzeczenie się:

To nie jest dowód (wydaje się, że niektórzy ludzie myślą, że opublikowałem to tak, jakby to było). To tylko niewielki eksperyment, który OP mógłby przeprowadzić, aby rozwiązać swoje wątpliwości dotyczące zadania:

bez względu na to, ile razy przechodzę przez to z odwróconą tablicą, wydaje mi się, że powinna to być a nie . $Θ(n^2)$ $Θ(n^3)$

Przy tak prostym kodzie różnica między i nie powinna być trudna do zauważenia, aw wielu praktycznych przypadkach jest to przydatne podejście do sprawdzania przeczuć lub dostosowywania oczekiwań. $\Theta(n^2)$ $\Theta(n^3)$

@Raphael już odpowiedział na twoje pytanie, ale tylko dla kopnięć, dopasowując dane wyjściowe tego programu do za pomocą tego skryptu gnuplot zgłosił wartości wykładników i i następujące wykresy ( pierwszy to skala normalna, a drugi to skala log-log): $f(x) = a\cdot x^b + c\cdot x$ $2.99796166833222$ $2.99223727692339$

Mam nadzieję, że to pomoże $\ddot\smile$

— dtldarek
źródło

2

Możesz dopasować dowolną funkcję do tych wartości. Zobacz także tutaj .

— Raphael

3

@ Rafael Jeśli nie chcesz w ten sposób nitpickować, to nie, nie możesz dopasować żadnej funkcji (na przykład nie będziesz w stanie dopasować stałej funkcji do żadnej rozsądnej dokładności). To nie jest dowód, ale już istnieje odpowiedź, która zapewnia szkic. Jeśli chodzi o użyteczność, mogę zacytować własny post, który podlinkowałeś: „Muszę się zgodzić, że jest to bardzo przydatne podejście, które czasami jest niedostatecznie wykorzystywane”. Co więcej, OP powiedział, że uważa, że powinno to być zamiast , więc dlaczego nie eksperymentować i sprawdzić, czy jego przeczucie było prawidłowe? Cd.

Θ (n^{2})

$\Theta(n^2)$

Θ (n^{3})

$\Theta(n^3)$

— dtldarek

2

Dowodzi to, że algorytmem jest ale pytanie brzmi: dlaczego . Prosi o wyjaśnienie tego zjawiska, a nie o jego potwierdzenie.

Θ (n^{3})

$\Theta(n^3)$

— David Richerby

2

@DavidRicherby Czy to oznacza, że ta odpowiedź nie jest przydatna?

— dtldarek

3

@Magicsowon To jest strona pytań i odpowiedzi, a nie forum. Szukamy odpowiedzi na pytanie, a nie dyskusji wokół niego.

— David Richerby,

3

Załóżmy, że masz tablicę.

array a[10] = {10,8,9,6,7,4,5,2,3,0,1}

Twój algorytm wykonuje następujące czynności

Scan(1) - Swap (10,8) => {8,10,9,6,7,4,5,2,3,0,1}  //keep looking at "10"
Scan(2) - Swap (10,9) => {8,9,10,6,7,4,5,2,3,0,1}
...
Scan(10) - Swap(10,1) => {8,9,6,7,4,5,2,3,0,1,10}

Zasadniczo przesuwa się na koniec tablicy najwyższy element, a robiąc to, zaczyna przy każdym skoku skutecznie wykonywać O(n^2)ruchy .. tylko dla tego jednego elementu. Jest jednak n elementów, więc będziemy musieli powtórzyć te nczasy. Nie jest to formalny dowód, ale pomaga zrozumieć w „nieformalny” sposób, dlaczego jest to czas działania O(n^3).

— Twórca gier
źródło

4

Co to dodaje do innych odpowiedzi? Wyjaśnienie działania algorytmu zostało już podane, a twoje rozumowanie środowiska wykonawczego jest co najwyżej szkicowe. (Najgorszy przypadek nie zachowuje się liniowo!)

— Raphael

2

Czasami warto objaśniać ten sam pomysł na wiele sposobów (z formalizmem; na prostym przykładzie „pompować intuicję”), szczególnie gdy osoba zadająca pytanie jest nowa w tej dziedzinie. Wydaje mi się więc, że to dodaje, że jest przedstawione w sposób, który może pomóc intuicji.

— DW

Ponieważ dostałem odpowiedź na mój komentarz w formie flagi (nie rób tego!): „Najgorszy przypadek nie zachowuje się liniowo!” - Mam na myśli właściwości algebraiczne operatora najgorszego przypadku. Z grubsza mówiąc, używasz WorstCase (1 + ... + n) "=" WorstCase (1) + ... + WorstCase (n), ale ta tożsamość się nie zachowuje.

— Raphael

1

Jestem nowy w tej dziedzinie i udzielenie wyjaśnienia konkretnym, przeliterowanym przykładem zdecydowanie pomogło mi uzyskać intuicję na temat problemu. Teraz zaakceptowane rozwiązanie ma dla mnie więcej sensu.

— vaer-k

0

Wygląda na to, że logika sortuje elementy w tablicy w porządku rosnącym.

Załóżmy, że najmniejsza liczba znajduje się na końcu tablicy (a [n]). Aby dojść do właściwego miejsca - wymagane są operacje (n + (n-1) + (n-2) + ... 3 + 2 + 1). = O (n2).

Dla pojedynczego elementu w tablicy wymagane są operacje O (n2). Tak więc dla elementów jest to O (n3).

— mk ..
źródło

5

Co to dodaje do innych odpowiedzi? Wyjaśnienie działania algorytmu zostało już podane, a twoje rozumowanie środowiska wykonawczego jest co najwyżej szkicowe. (Najgorszy przypadek nie zachowuje się liniowo!)

— Raphael

Świetne wyjaśnienie. Zapewnia to inną, bardziej intuicyjną perspektywę problemu, nie wyjaśnioną w innych odpowiedziach. (Nie wspominając o bardzo krótkim i łatwym do zrozumienia.)

— 2501

1

@ 2501 Nie, to źle. Spróbuj użyć tej „intuicji” w algorytmie Dijkstry, a otrzymasz kwadratowy czas działania (w liczbie węzłów), co jest nieprawidłowe.

— Raphael

@Raphael Nie, to prawda, jak wyjaśniono w odpowiedzi. To wyjaśnienie działa dla tego algorytmu, a nie dla innych. Chociaż może to być dla nich złe, to twierdzenie nie dowodzi, że jest złe dla tego.

— 2501

@ Rafael Nie zrozumiałem wyjaśnienia w przyjętej odpowiedzi. Więc rozwiązałem ten problem i starałem się wyjaśnić to w prosty sposób, bez żadnych terminów technicznych .. więc, to jest dla członków takich jak ja, którzy nie mogli zrozumieć zaakceptowanej odpowiedzi .. Cieszę się, że ktoś uważa to za przydatne.

— mk ..