Krótkie Wprowadzenie Do Analizy Asymptotycznej

Notacja Asymptotyczna

1. Co to jest?

Notacja Asymptotyczna służy do opisywania czasu wykonywania się algorytmu, w zależności od wielkości danych, im dane wieksze, tym zależność dokładniejsza - tym sposobem łatwiej widać, które rozwiązania dadzą bardzo długie obliczenia. Przykład: załóżmy, że najgorszy czas wykonywania się jakiegoś programu to:
a) an^2 + bn + c,
Piszemy, że ten algorytm jest O(n^2) - Big - O n^2, czyli abstrahujemy od liniowych i stałych czynników i definiujemy, iż jest asymptotycznie ograniczony z góry funkcją kwadratową(n, n0 są wszędzie nieujemnymi liczbami całkowitymi, n reprezentuje wielkość danych).

2. Definicje.

Θ (teta)
Teta - Θ oznacza, że jakaś funkcja jest ograniczona z góry i z dołu inną funkcją:

Algorytm jest Θ(g(n)), to znaczy, że
Dla danej funkcji g(n), Θ(g(n)) to zbiór:
Θ(g(n)) = {ogół takich f(n), że: istnieją, większe od zera stałe c1, c2 i n0, takie że
0 <= c1 g(n) <= f(n) <= c2 g(n), dla wszystkich n >= n0}.

Jeśli funkcja należy do zbioru Θ(g(n)), to piszemy również f(n) = Θ(g(n)).
Na przykład, dowolna funkcja kwadratowa (taka jak w par. 1 a) ) jest Θ(n2).

O (Big - O)

Big - O - asymptotyczne ograniczenie górne czasu wykonywania się algorytmu:

Program jest O(g(n)), czyli dla danej funkcji g(n), O(g(n)) to zbiór:
O(g(n)) = {ogół takich f(n): istnieją dodatnie stałe c i n0, takie że
0 <= f(n) <= c g(n), dla każdego n >= n0}.

Tak samo piszemy:

f(n) = O(g(n)),

gdy funkcja f należy do zbioru O(g(n)) (należy uważać na tę dwuznaczność znaku równości). Na przykład, 3n^2 + 5n = O(n^3) ale nie Θ(n^3).

Ω (Omega)
Ω - Tak jak Big - O to asymptotyczne ograniczeniez góry, to Ω to asymptotyczne ograniczenia z dołu.

Algorytm jest Ω(g(n)), tzn. dla danej funkcji g(n), Ω(g(n)) (zbiór):
Ω(g(n)) = { ogół takich f(n): istnieją dodatnie stałe c i n0:
0 <= c g(n) <= f(n), dla każdego n >= n0}.

Oznaczając tę przynależność, piszemy:

f(n) = Ω(g(n)).

Na przykład dowonla funkcja kwadratowa (taka jak z 1. a)) jest Ω(n^2). Oczywiście,
funkcja f(n) = Θ(g(n)) wtedy i tylko wtedy gdy f(n) = O(g(n)) i f(n) = Ω(g(n)).

o

Notację małe - o stosujemy gdy chcemy pokazać asymptotycznie ostre ograniczenie funkcji(nie dopuszczamy <=); generalnie Big - O nie jest asymptotycznie ostre(dopuszczamy <=); np., an^2 = O(n^2) jest, ale 5n = O(n^3) nie jest.

Definiujemy o(g(n)): dla danej funkcji g(n), o(g(n)) (zbiór):
o(g(n)) = {ogół takich f(n): dla każdej dodatniej stałej c, istnieje stała n0, taka że:
0 <= f(n) < c g(n)}.

Czyli an = o(n^2), ale an^2 nie równa się o(n^2). W tym przypadku zachodzi, również:
Granica, gdy n dąży do nieskończoności z f(n)/g(n) wynosi zero. Widać też wyraźną różnicę: tutaj dla każdej stałej c, a w przypadku Big - O istnieje taka stała - dlatego też funkcje te nie mogą być równe. I analogicznie

ω
Notacja ω - czyli to samo dla Ω, czym jest o - notacja dla Big - O - ogranicznie dolne asymptotycznie ostre.

Funkcja jest ω(g(n)); ω(g(n)) jest zbiorem:
ω(g(n)) = {ogół f(n): dla każdej stałej c istnieje stała n0, taka, że:
0 <= c g(n) < f(n)}.

Na przykład n^2 / 5 = ω(n), ale nie ω(n^2). Oczywiście piszemy równość f(n) = ω(g(n)), i zachodzi też:
Granica przy n dążącym do nieskończoności z f(n) / g(n) = nieskończoność.

3. Funkcje asymptotyczne w wyrażeniach.

Do tej pory analizowaliśmy definicje w których znak równości oznaczał relację należenia pewnej funkcji do zbioru; ale można też używać asymptot w równaniach i nierównościach, jeśli n = O(n^2), to rozpatrzmy:

3n^2 + 2n - 1 = 3n^2 + Θ(n)

Znak równości nie będzie tu symbolem należenia do zbioru - to oczywiste; symbol Θ interpretujemy więc jako dowolną funkcję (anonimową), czyli tutaj będzie to jakieś f(n) rzędu Θ(n), f(n) = 2n - 1.
To pozwala nam abstrahować przy analizie czasu algorytmów (i upraszczać ).

3. Case Study - Mergesort.

Jako case study wybrałem Mergesort, dla wygody napisany w Pythonie:

# merge sort
def merge(alist, lefthalf, righthalf):
    i = 0
    j = 0
    k = 0
    while i < len(lefthalf) and j < len(righthalf):
        if lefthalf[i] < righthalf[j]:
            alist[k] = lefthalf[i]
            i += 1
        else:
            alist[k] = righthalf[j]
            j += 1
        k += 1
    while i < len(lefthalf):
        alist[k] = lefthalf[i]
        i += 1
        k += 1
    while j < len(righthalf):
        alist[k] = righthalf[j]
        j += 1
        k += 1

def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)
        merge(alist, lefthalf, righthalf)

Klasyczny algorytm dziel i rządź (co czyni go idealnym dla prostej analizy asymptotycznej). Ile pracy wykonuje ten algorytm?

Patrząc na procedurę merge, nietrudno zauważyć, że wykonuje ona ilość operacji proporcjonalną do n:
Mamy pewną stałą ilość instrukcji (oznaczaną zwyczajowo Θ(1)), n iteracji pierwszej pętli while, oraz n1 + n2 iteracji pozostałych dwóch pętli (gdzie n1 i n2 jest równe n / 2); czyli Θ(n1 + n2 + n) = Θ(n) (ponieważ 2n czy 3n czy ogólnie a razy n jest równe Θ(n)).

Cały algorytm:
Problem rozmiaru T(n), jest wykonywany rekurencyjnie, czyli w każdym wywołaniu wykonuje:

• Dzielenie tablicy - operacja stała Θ(1);
• Rekurencyjne wywołanie problemu o mniejszej złożoności - wiadomo dlaczego musi być mniejsza- większej lub równej nie miałoby sensu: algorytm by powiększał lub w nieskończoność wykonywał tę samą ilość pracy. W tym wypadku są dwa wywołania pod - problemu 2 razy mniejszego czyli T(n) zamienia się w T(n/2) + T(n/2);
• Połączenie już rekurencyjnie wywołanych tablic - to procedura merge - czyli plus jeszcze Θ(n).

Sumując to wszystko i układając w relację rekurencyjną mamy:

T(n) = Θ(1), gdy n = 1 (base case)
T(n) = 2T(n/2) + Θ(n), gdy n > 1

Wybiegając w przyszłość - Master Theorem:) (co sugeruje możliwy ciąg dalszy), rozwiązaniem tej rekurencji jest:

T(n) = Θ(nlog(n)).

Czyli merge sort należy do Θ(nlogn).

To by było na tyle, mam nadzieję, że ten krótki "cheatsheet" okaże się przydatny!