TI/Algorytmy i struktury danych/Złożoność obliczeniowa i pamięciowa

Złożoność obliczeniowa i pamięciowa

Złożoność obliczeniowa -- założenia

Jak wiadomo, czas wykonania programu może się różnić w zależności od tego na jak silnym komputerze zostanie on wykonany. Dlatego w dla potrzeb teoretycznego porównywania złożoności czasowej różnych algorytmów, nie mierzymy jej w sekundach, tylko abstrakcyjnych jednostkach -- ilości "operacji dominujących", czyli takich, które znacząco wpływają na czas wykonania programu.

Wskaż operacje dominujące w poniższych programach:

def suma(a,b):
   wynik = a + b
   return wynik

def operacje(a,b):
   suma = a+b
   iloczyn = a*b
   iloraz = a/b
   roznica = a - b
   return suma, iloczyn, roznica, iloraz

def wypisz(a,b):
   print operacje(a,b)

(Wywołanie funkcji która ma 4 instrukcje, będzie trwać 4 instrukcje)

Znajdowanie Maximum: Danych jest N różnych liczb, nazwanych A[1], ... , A[N]. Wskaż największą.

m = A[1]
imax = 1 
for i = t to N do:
   if A[i] > m:
       m = A[i]
       imax = i

Problem: Wskaż index wystapienia liczby 0 w danej tablicy. Wiadomo, że występuje dokładnie raz.

 for i=1 1 to N do:
  if A[i] = 0:
   return i

Jaki będzie koszt dla danych:

A[1] =  1, A[2] = 0, A[3] = 1, A[1000] = 1

A dla danych:

A[1] = 1, ... , A[999] = 1, A[1000] = 0

Sortowanie bąbelkowe:

sort(T)
  for i=0 to n-2 do
       for j=n-1 downto i+1 do
            if (t[j-1]>t[j])
                 zamień t[j] i t[j-1]

• Która operacja jest tu operacją, którą bierzemy pod uwage przy szacowaniu kosztu?
• Ile będzie trwało sortowanie dla tablicy:
  • t[1] = 2, t[2] = 3, t[3] = 1, t[4] = 4, ..., t[100] = 100
  • t[1] = 2, t[2] = 3, t[3] = 1, t[4] = 4, t[5] = 6, t[6] = 5, ..., t[100] = 100

• A jakie są najgorsze możliwe dane? Ile wtedy będzie trwało wykonanie programu?

Na tym właśnie polega szacowanie kosztu pesytmistycznego -- czas trwania programu dla najgorszych możliwych danych.

Koszt pesymistyczny i oczekiwany

Dla zainteresowanych koszty różnych operacji w pythonie tutaj

Ćwiczenia

• Jakie będą złożoności obliczeniowe następujących pętli:

    for i in range(n)
        print i


    for j in range(n)
        for i in range(n)
             print i, j


    for j in range(n):
        for i in range(j):


    n=1
    while(n < =x):
        print n
        n=2*n
    

    h=n
    while(h > 0):
        for i in range(n):
            print i
        h=h/2

Notacja duże "O" i rzędy wielkości

Notacja duże "O" (inaczej: notacja asymptotyczna, notacja Landaua) służy do opisywania asymptotycznego zachowania funkcji (czyli zachowania funkcji wraz ze wzrostem jej argumentów).

Definicja:

f(x) = O(g(x)) <=> istnieje c>0 i x_0 > 0 takie, że dla każdego x > x_0 zachodzi f(x) <= cg(x) 

Oznacza to, że f jest co najwyżej rzędu g.

Porównywanie złożoności:

1 < lg(lg(n)) < lg(n) < sqrt(n) < n < nlg(n) < n^2 < n^3 < n^{lg(n)} < 2^n < n! < n^n <2^{2^n}

Ćwiczenie

• Załóżmy, że algorytmy A i B rozwiązują ten sam problem. Niech program A ma koszt pesymistyczny 100*n*log2(n), a program B n^2.

• • Czy zawsze bardziej się opłaca użyć algorytmy A?
  • Co będzie dla danych, gdzie n >> 10000 ?
  • Co będzie dla danych, gdzie n << 100 ?

Sortowanie przez wstawianie

Elementy tablicy od 1 do i - 1 są posortowane, w kolejnym kroku należy w odpowiednie miejsce wstawić element a[i], w tym celu szukamy pierwszego elementu mniejszego od a[i] występującego przed nim i aktualny element wstawiamy bezpośrednio za nim (wymaga to przesunięcia wszystkich elementów za znalezionym o jedno miejsce w prawo)

for i := 2 to n do
begin
 x := a[i];
 j := i - 1;
 while (j > 0) and (a[j] > x) do
 begin
  a[j - 1] := a [j];
  j := j - 1;
 end;
 a[j] := x;
end;

Operacjami dominującymi są przypisania w liniach 3 i 7

Gdy tablica a na początku jest już posortowana rosnąco to operacja dominująca wykona się dokładnie n - 1 = O(n) razy (nigdy nie będzie spełniony warunek a[j] > x), a w sytuacji gdy będzie ona posortowana malejąco to warunek ten będzie zawsze spełniony, zatem dla k-tego przebiegu for pętli pętla while wykona się k - 1 razy, zatem złożoność obliczeniowa to: 1 + 2 + 3 + ... + (n - 1) + n = n(n - 1) / 2 + n - 1 = O(n^2), widać, zatem, że złożoność może zależeć od danych wejściowych

Na szczęście gorzej już się nie da - o drugim przypadku mówimy, że jest pesymistyczny, a jego złożoność nazywamy złożonością pesymistyczną.

Złożoność oczekiwana

W codziennej praktyce spotykamy dość rzadko dane realizujące złożoność pesymistyczną, zatem nasuwa się pytanie jak szybko będzie działał nasz program zazwyczaj, czyli chcemy znać złożoność oczekiwaną bądź średnią.

Zastanówmy się najpierw od czego zależy liczba przypisań w linii 7, jest ona związana z liczbą inwersji, czyli liczbą takich par (i,j), że j > i i a[j] < a[i], oznaczmy ją inv(a), wtedy liczba wykonań operacji dominującej to n - 1 + inv(a), zatem jeśli inv(a) = O(n) to złożoność całego algorytmu jest O(n), a gdy inv(a) = O(n^2) to taka jest również złożoność algorytmu.

Postarajmy się teraz obliczyć średnią liczbę inwersji w losowej permutacji.

Do obliczania złożoności oczekiwanej przydatna jest znajomość rachunku prawdopodobieństwa, n-elementowych permutacji mamy n!, załóżmy, że każda jest równie prawdopodobna

Pozostaje teraz policzyć ile jest permutacji mających dokładnie k inwersji, pomocnym do tego będzie wprowadzenie pojęcia wektora inwersji permutacji, czyli ciąg w[i], gdzie w[i] to liczba elementów występujących na lewo od a[i] w ciągu a i większych od a[i], czytelnikowi pozostawiamy udowodnienie bijekcji między permutacją i odpowiadającym jej wektorem inwersji, oczywiste jest, że suma elementów wektora inwersji jest równa liczbie inwersji permutacji, na pozycji i w wektorze inwersji mogą się znaleźć (z równym prawdopodobieństwem wynoszącym 1/i) liczby od 0 (gdy a[i] jest większe od wszystkich poprzednich) do i - 1 (gdy a[i] jest mniejsze od wszystkich poprzednich), zatem wartość oczekiwana i-tego elementu to (0 + 1 + 2 + ... + (i - 1)) / i = (i - 1) / 2, a wartość oczekiwana sumy elementów wektora inwersji to 0 + 1 / 2 + 2 / 2 + ... + (n - 1) / 2 = n(n - 1) / 4

Zatem dla losowej permutacji a mamy inv(a) = n(n - 1) / 4, zatem oczekiwana złożoność algorytmu sortowania przez wstawianie to: n(n - 1) / 4 + n - 1 = O(n^2)

Zadania

• wymyśl program, którego złożoność będzie wynosiła:
  • O(n^2) (np. psortowanie bąbelkowe, sortowanie przez wstawianie (insertion sort), sortowanie przez wybór (selection sort))
  • O(n!) (dopasowywanie kwadracików z dzióbkami - układanka, problem skoczka)
  • O(n) (szukanie lidera, szukanie najdłuższego niespójnego ciągu rosnącego)
  • O(1)
  • O(2^n) (obliczanie liczby Fibonacciego, wieże Hanoi)
  • O(lg(n)) (wyszukiwanie binarne)
  • O(nlg(n))

Przykłady

Problem sortowania: dana jest tablica należy ją posortować, czyli ustawić jej elementy w kolejności rosnącej (albo malejącej)

Sortowanie bąbelkowe

Badamy tablicę od początku jeśli znajdziemy takie i, że a[i + 1] < a[i] to zamieniamy elementy, po jednym przejściu tablicy na ostatnim miejscu otrzymujemy największy element tablicy, problem redukuje się zatem do tablicy krótszej o 1

for i := 1 to n - 1 do
begin
 for j := 1 to n - i + 1 do 
 begin
  if a[j + 1] < a[j] then
   swap(a[j + 1], a[j]);
 end;
end;

Sortowanie przez wstawianie

patrz opis złożoności pesymistycznej i oczekiwanej

Sortowanie przez wybór

Przechodzimy tablicę szukając elementu największego zamieniamy go z ostatnim po czym problem redukuje się do sortowania tablicy krótszej o 1

for i := 1 to n do
begin
 max := a[i];
 maxIndex := i;
 for j := 1 to n - i + 1 do
 begin
  if a[j] > max then
  begin
   max := a[j];
   maxIndex := j;
  end;
 end;
 swap(a[maxIndex], a[n - i + 1]);
end;

Dopasowanie kwadracików z dzióbkami :-)

M amy dane m = n^2 kwadracików przy każdym boku kwadratu wewnątrz niego znajduje się kolorowy trójkąt, należy sprawdzić czy istnieje takie ułożenie kwadratów w jeden duży o boku n, że wszystkie trójkąty pasują do siebie - najprostsze rozwiązanie to sprawdzenie wszystkich możliwości których jest m!

Szukanie lidera

dany jest ciąg a[1..n], problem polega na znalezieniu elementu występującego w nim więcej niż n/2 razy, rozwiązanie brutalne to sprawdzenie liczności występowania każdego z elementów - złożoność kwadratowa, można to jednak zrobić w czasie liniowym :-)

wystapienia := 0;
for i := 1 to n - 1 do
begin
 if wystapienia = 0 then
 begin
  kandydat := i;
  wystapienia := 1;
 end;
 if a[i] = a[i + 1] then
  wystapienia := wystapienia + 1;
 else
  wystapienia := wystapienia - 1;
end;

w zaskakujący automagiczny sposób jeśli w tablicy występował lider to jest nim a[kandydat], sprawdzić czy jest on liderem możemy oczywiście w czasie liniowym

Szukanie najdłuższego niespójnego podciągu rosnącego (malejącego)

Najbardziej brutalna metoda to wygenerowanie wszystkich 2^n podciągów i sprawdzanie po kolei, ale da się to zrobić w czasie O(nlogn).

 odp = 1
 for i in range(n): 
  x = a[i]
  a[i] = 0
  # poniezej szukamy minimalnego j, t. ze j<= i, oraz x >= a[j]
  
  while (j >= 0) and (x >= a[j]):
   j := j - 1
  a[j] = x
  odp = max(j, odp)

Powyższy algorytm rozwiązuje problem wciąż w czasie O(n^2), ale można go łatwo sprowadzić do O(nlogn) dzięki temu, że początek tablicy, w którym wyszukujemy minimum, będzie zawsze posortowany i możemy zastosować przeszukiwanie binarne.

Obliczanie liczby Fibonacciego

Liczbę Fibonacciego definiuje się rekurencyjnie: [math]F_0 = 0; F_1 = 1; F_{n} = F_{n - 1} + F_{n - 2}[/math], można ją liczyć z definicji daje to [math]2^n[/math] dodawań, są do tego inne techniki można na przykład zaalokować dodatkową zmienną i trzymać w niej poprzedni wynik korzystając z niego i aktualizując go za każdym razem — daje to złożoność liniową, można robić to metodą mnożenia macierzy, co przy zastosowaniu metody mnożenia chłopków syberyjskich da złożoność logarytmiczną i w końcu dla większych [math]n[/math] można skorzystać ze wzoru Bineta i dostać przybliżony wynik w czasie stałym. Tytuł linku

Wieże Hanoi

Wyobraźcie sobie trzy słupy na jeden z nich są nasunięte krążki o malejącym idąc w górę promieniu, zasady: możecie kłaść krążek tylko na krążek o większej średnicy albo wkładać na pusty słup, zadanie dla Was przełożyć n krążków ze słupa numer 1 na słup numer 2 korzystając ze słupa numer 3, czas start! jeśli przełożycie 64 takich krążków to zgodnie z wierzeniami tybetańskich mnichów nastąpi koniec świata (biorąc pod uwagę złożoność jest to możliwe), jak to zrobić? jednym ze sposobów jest podejście rekurencyjne, zadanie sprowadza się do:

przełożyć n - 1 krążków ze słupa numer 1 na słup numer 3 korzystając ze słupa numer 2 przełożyć krążek ze słupa numer 1 na słup numer 2 przełożyć n - 1 krążków ze słupa numer 3 na słup numer 2 korzystając ze słupa numer 1

daje to złożoność 2^n

Wyszukiwanie binarne

Legenda głosi, że był kiedyś teleturniej w którym występowały dwie drużyny, jedna wymyślała słowo, a druga miała za zadanie zadając określoną liczbę pytań odgadnąć to słowo, pech chciał, że do gry zgłosili się kiedyś studenci MIMUW, pierwsze ich pytanie brzmiało: "czy to słowo to żaba?" przeciwnicy odetchnęli z ulgą, najwyraźniej jacyś mocno nieogarnięci przyszli - pomyśleli i odpowiedzieli, że nie, po tym dzielni studenci otworzyli słownik w środku i zadali pytanie: "czy to słowo jest w słowniku przed czy po X", gdzie X to słowo znajdujące się w okolicy połowy słownika, po odpowiedzi wiedzieli już w której części słownika należy szukać słowa, robiąc tak dalej odgadli słowo bez problemu

Problem skoczka

Mamy szachownicę n na n pól i pytanie: czy jest możliwe aby skoczek odwiedził wszystkie pola dokładnie raz? rozwiązanie brutalne wymaga dodatkowej tablicy n x n w której będziemy zaznaczać czy odwiedziliśmy już dane pole czy nie i sprawdzenia wszystkich możliwości

Złożoność pamięciowa

Złożoność pamięciową mierzymy w liczbie komórek pamięci komputera zajmowanych przez program. Tu znów dla uproszczenia będziemy się skupiać na tym ile zajmują "właściwe" dane, na których program wykonuje operacje oraz -- żeby uniknąć problemów związanych z typami i reprezentacją liczba -- dla uproszczenia zakładamy, że jedna liczba / komórka tablicy / innej struktury zajmuje jedną "jednostkę". (Chyba że w zadaniu jest explicite powiedziane, że jest inaczej.) Także omówiony wyżej program, który ma znajdywać maximum w tablicy N elementowej będzie miał złożoność pamięciową O(N).

Przykłady:

Ciekawostka -- oszczędzanie na każdej zmiennej

Napisz program, który zamieni wartościami zmienne a i b. Tzn jeśli na początku a = 1, b = 2, to wynikiem działania programu ma być a = 2, b = 1.

 c = a
 a = b
 b = c

Potrzebujemy aż 3 komórek pamięci. Czy da się oszczędniej?

 a = a + b 
 b = a - b 
 a = a - b

Sortowanie przez zliczanie:

Mamy tablicę t, N liczb naturalnych do posortowania. Poznaliśmy już kilka algorytmów, które nam pozwolą ją posortować w czasię O(N^2). Teraz załóżmy, że mamy dodatkową informację o tych liczbach -- są one z zakresu 1 do M. Możemy zastosować taki trick:

• alokujemy tablicę pom, długości M, wypełnioną zerami.
• przechodzimy tablicę t, i wykonujemy operację pom[t[i]] += 1
• teraz wystarczy przejść raz tablicę pom, i utworzyć tablicę która ma na pierwszych pom[1] miejscach jedynki, pom[2] miejscach dwójki, itd, która będzie naszym wynikiem

• Jaki wpływ ma ten trick na złożoność obliczeniową, a jaki na pamięciową sortowania?

W przypadku gdy na przykład M = O(NlogN) poprawia to złożoność czasową algorytmu, natomista pogarsza złożoność pamięciową.

• Cobędzie, gdy M << N?

Załóżmy teraz, że M << N. Wtedy takie sortowanie poprawia złożoność czasową nie pogarszając pamięciowej O(M + N).

• Załóżmy, że tym razem jednak interesuje nas zachowanie pierwotnej kolejności tych liczb. To znaczy dwie liczby "3" traktujemy jako w pewien sposób różne, i mają pozostać względem siebie w pierwotnej kolejności ("stabilność" sortowania). Czyli liczby są pewnego rodzaju obiektami. Zaalokujmy zatem w tablicy pom tablice, w których będizemy przechowywać obiekty, w takiej kolejności, w jakiej je spotkamy, a już nie tylko ilość ich wystąpień.

Jaka będzie w tej sytuacji złożoność pamięciowa i obliczeniowa?

Złożoność czasowa pozostaje taka sama, natomiast złożoność pamięciowa zwiększa się do O(M * N).

Jakie złożoności pamięciowe mają poznane algorytmy sortowania:

• bąbelkowe (przykład wyżej)
• przez wstawianie (przykad wyżej)
• selection sort (przez wybór za każdym razem najmniejszego elementu i wstawienie go w odpowiednie miejsce)

Koszt zamortyzowany

Czasami w praktyce dana operacja "na ogół" będize miała koszt 1, ale w najgorszym przypadku może mieć koszt O(N). Jednak wiemy, że zdarzy się to raz na N przypadków, i wiemy to w sposób deterministyczny. Wtedy ten koszt O(N) rozłoży się równomienie na te N przypadków, co spowoduje, że każdą operację będizemy mogli traktować jakby miała koszt O(2), w każdym razie stały. Mówimy wtedy o koszcie zamortyzowanym.

Dobrym przykładem jest tablica dynamiczna, jej implementacja polega na tym, że początkowo bierzemy tablicę pewnej długości na przykład 2, wstawiamy do niej elementy (w czasie stałym), a gdy pojemność tablicy się kończy to alokujemy nową dwukrotnie większą i tu musimy przepisać wszystkie elementy (w czasie liniowym), zatem wkładając n elementów mamy 2 + 4 + 8 + ... + floor(lg(n)) + n = 2(floor(lg(n)) - 1) + n przypisań przy n operacjach, zatem koszt zamortyzowany to 1 + 1 / n + 2(floor(lg(n)) - 1)