Tekst źródłowy strony TI/Algorytmy i struktury danych/Złożoność obliczeniowa i pamięciowa


<!--= szkic =
* '''trochę o tym, jak taki program będzie się wykonywał w uproszczony sposób: zaujmuje jakieś miejsce w RAM oraz wykonuje różne instreukcje po kolei'''
* '''różne "linijki" programu trwają jakąś jednostkę czasu. zakładamy, ze każda instrukcja trwa taką samą. Kilka przykładów w którcych studenci mają wskazać co jest instrukcjami które będziemy zliczać. Bardzo prostych -- w czasie stałycm albo liniowym. Niech będzie choćby wyszukiwanie . NA razie obliczanie ile to zajmie w przypadku jakichś koonkretnych danych wejściowych'''
* koszt obliczeniowy pesymistyczny i oczekiwany. Wskazywanie najbardziej pechowych danych wejściowych. Zgadywanie jaki rozkład mogą mieć dane wejściowe.
* dalej przykład trudniejszy do oszacowania. Od niego przejście do szacowania i porównywania podstawowych rzędów wielkości funkcji (przykład – 10 minut na zastanowienie, 10 minut na omowienie odpowiedzi, 25 minut na porównywanie różnych rzędów wielkośći)
* przykłady programów/algorytmów w których te rzędy wielkości ładnie widać
* '''złożoność pamięciowa -- rozmiar danych wejściowych oraz struktury alokowane w trakcie działania programu. To będzie przydatne w tłumaczeniu po co są listy. O tym chyba dokładniej przy omawianiu struktur danych'''
* proste obliczanie kosztu zamortyzowanego
* Szacowanie ile czasu rzeczywistego zajmie wykonanie programu, '''nauczenie intuicji jak długo trwa instrukcja wypisania/prostego obliczenia itp'''
* '''to, że w praktyce jeśli robimy jakieś wypisanie, to to trwa dużo dłużej niż jakieś pojedńcze przypisanie/obliczenie, różne ćwiczenia ile w praktyce trwa wykonanie programu'''
*'''Problemy P i np.'''
-->

= 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:
<source lang="python">
def suma(a,b):
   wynik = a + b
   return wynik
</source>

<source lang="python">
def operacje(a,b):
   suma = a+b
   iloczyn = a*b
   iloraz = a/b
   roznica = a - b
   return suma, iloczyn, roznica, iloraz
</source> 


<source lang="python">
def wypisz(a,b):
   print operacje(a,b)
</source>
(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.
<source lang="python">
 for i=1 1 to N do:
  if A[i] = 0:
   return i

</source>

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 [http://wiki.python.org/moin/TimeComplexity tutaj]



=== Ćwiczenia ===

* Jakie będą złożoności obliczeniowe następujących pętli:
<source lang="python">
    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

</source>

=== 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)) 


<!-- zakładając, że pojedyncza instrukcja trwa mikrosekundę to... policzyć ile będzie trwało wykonanie programu dla n = 10, 20, 40, 80, 160, 320, 640 instrukcji przy różnych złożonościach, zrobić wykresy funkcji w gnuplocie-->



=== 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).

<!--pomyślmy, że mamy tablicę t w której na miejscu k-tym jest minimalna wartość na której kończy się jakiś z k-elementowych podciągów ciągu a, jeśli takiego ciągu nie ma to w tablicy jest inf, teraz rozwiązanie jest trywialne - szukamy największego k, takiego, że t[k] != inf, zastanówmy się jak zbudować taką tablicę na pewno dobrym początkiem będzie t[1] := a[1], teraz patrzymy na kolejny element jeśli jest on mniejszy od t[1] to należy wykonać t[1] := a[2], a jeśli większy to t[2] := a[2] no to już wiemy: -->
<!-- t[1] := a[1]; -->
<!-- for i := 1 to n do
 begin
  j := i - 1;
  while (j > 0) and (a[i] < a[j]) do
   j := j - 1;
  if j = 0 then
   j := 1;
  t[j] := a[i];
 end;
-->
<source lang="python">
 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)
</source>

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 &mdash; 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

<!--algorytm potęgowania chłopków syberyjskich :-) czyli potęgowanie w czasie logarytmicznym przez zamianę wykładnika na postać binarną i korzystanie z poprzedniego wyniku
-->

== 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.
<source lang="python">
 c = a
 a = b
 b = c
</source>

Potrzebujemy aż 3 komórek pamięci. Czy da się oszczędniej?
<source lang="python">
 a = a + b 
 b = a - b 
 a = a - b
</source>

==== 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)

<!-- == Problemy P i NP ==
Klasą P nazywamy zbiór tych zadań algorytmicznych, dla których istnieją algorytmy rozwiązujące je w czasie wielomianowym. 
Klasą NP nazywamy zbiór tych zadań algorytmicznych, które można weryfikować w czasie wielomianowym, tzn znając rozwiązanie można sprawdzić je w czasie wielomianowym. Skróty P i NP pochodzą z angielskiego, odpowiednio, polynomial time i nondeterministic polynomial time.

Algorytmy klasy NP są bardzo użyteczne w kryptografii.
-->