Analiza algorytmów (złożoności)

Question

W jaki sposób analizowane są algorytmy? Co sprawia, że ​​quicksort ma najgorszą możliwą wydajność, gdy sortowanie scalone ma najgorszą możliwą wydajność?

Answer 1

To jest temat na cały semestr. Ostatecznie mówimy o górnej granicy liczby operacji, które muszą zostać zakończone, zanim algorytm zakończy się w zależności od rozmiaru danych wejściowych. Nie uwzględniamy współczynników (tj. 10N vs 4N^2), ponieważ dla N wystarczająco duży, nie ma to już znaczenia.

Jak udowodnić, czym jest wielki algorytm, może być dość trudne. Wymaga formalnego dowodu i jest wiele technik. Często dobrą metodą adhoc jest po prostu policzenie liczby przebiegów danych, które tworzy algorytm. Na przykład, jeśli twój algorytm zagnieździł się dla pętli, to dla każdego z N elementów musisz operować N razy. To na ogół będzie O (N^2).

Aby scalić sortowanie, dzieli się dane na połowę raz po raz. To wymaga log2 (n). I dla każdego podziału przekazujesz dane, które dają N log (n).

sortowanie szybkie jest nieco trudniejsze, ponieważ w przypadku przeciętnym jest to również n log (n). Musisz sobie wyobrazić, co się stanie, jeśli twoja partycja podzieli dane tak, że za każdym razem otrzymasz tylko jeden element z jednej strony partycji. Następnie musisz podzielić dane n razy zamiast log (n) razy, co powoduje, że N^2. Zaletą quicksort jest to, że można to zrobić na miejscu i że zwykle zbliżamy się do wydajności N log (n).

Answer 2

Zarówno quicksort, jak i merge sort dzielą tablicę na dwie części, sortują każdą część rekurencyjnie, a następnie łączą wynik. Quicksort dzieli się, wybierając element "pivot" i dzieląc tablicę na mniejsze lub większe niż pivot. Scal sortuje podziały dowolnie, a następnie łączy wyniki w czasie liniowym. W obu przypadkach pojedynczym krokiem jest O (n), a jeśli wielkość tablicy jest za każdym razem o połowę, daje to logarytmiczną liczbę kroków. Tak więc oczekiwalibyśmy O (n log (n)).

Jednak quicksort ma najgorszy przypadek, w którym podział jest zawsze nierównomierny, więc liczba kroków nie jest proporcjonalna do logarytmicznej liczby n, ale liczba kroków jest proporcjonalna do n. Scal sort dzieli dokładnie na dwie połówki (lub tak blisko jak to możliwe), więc nie ma tego problemu.

Answer 3

• Szybkie sort ma wiele wariantów, w zależności od wyboru przegubu
• Załóżmy, że zawsze wybierać 1. pozycję w tablicy jako pivot

Jeśli tablica wejście jest klasyfikowane następnie szybkiego sortowania będzie tylko rodzaj sortowania sortowania! Ponieważ tak naprawdę nie dzielisz tablicy .. tylko wybierasz pierwszy element w każdym cyklu. Z drugiej strony sortowanie scalone zawsze podzieli tablicę wejściową w ten sam sposób, niezależnie od jej zawartości!

Uwaga: najlepsza wydajność w podziale i podbiciu, gdy długość działki jest równa - mniej więcej równa!

Answer 4

1. To jest wstępna analiza materiału kursu algorytmów.

2. Operacja jest zdefiniowana (tj. Mnożenie), a analiza jest wykonywana w postaci spacji lub czasu.

3. Ta operacja jest liczona w czasie lub przestrzeni.Zazwyczaj analizy są wykonywane jako czas będący zmienną zależną od wielkości wejściowej.

Przykład pseudokod:

foreach $elem in @list 

    op(); 

endfor 

Będzie n operacje wykonywane, gdzie n ma wielkość @list. Policz to sam, jeśli mi nie wierzysz.

Aby analizować quicksort i mergesort wymaga przyzwoitego poziomu tak zwanego wyrafinowania matematycznego. Luźno, rozwiązujesz dyskretne równanie różniczkowe wyprowadzone z relacji rekursywnej.