====== Złożoność algorytmów ======

**Termin zajęć:** 29/30.03.2011

**Do przygotowania:**
  - Znajomość i rozumienie pojęć:
    - Złożoność obliczeniowa.
    - Złożoność pamięciowa:
      - Działanie algorytmów "w miejscu".
    - Złożoność pesymistyczna.
    - Złożoność oczekiwana.
    - Złożoność optymistyczna.
**Zajęcia odbywać się będą głownie przy tablicy**.
Nie ma konieczności przynoszenia laptopów.

----

=== Metoda rekurencji uniwersalnej ===
Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci: \\ <latex>T(n) = aT(n/b)+f(n)</latex>  gdzie:
    * a ≥ 1
    * b > 1
    * f(n) jest funkcją asymptotycznie dodatnią.
    * iloraz <latex>n/b</latex> interpretujemy jako <latex>\lceil n/b \rceil</latex> lub jako <latex>\lfloor n/b \rfloor</latex>
Wtedy **T(n)** może być ograniczona asymptotycznie w następujący sposób:
      - Jeżeli <latex>f(n) = O(n^{\log_{b}(a)-\epsilon})</latex> dla pewnej stałej ε > 0 to, <latex>T(n) = \Theta(n^{\log_{b}(a)})</latex>
      - Jeśli <latex>f(n) = \Theta(n^{\log_{b}(a)})</latex> to, <latex>T(n) = \Theta(n^{\log_{b}(a)}\lg(n))</latex>
      - Jeżeli <latex>f(n) = \Omega(n^{\log_{b}(a)+\epsilon})</latex> dla pewnej stałej ε > 0 oraz <latex> af(n/b) \leq cf(n)</latex> dla pewnej stałej **c** i wszystkich dostatecznie dużych **n**, to <latex>T(n) = \Theta(f(n))</latex>

=== Zadania ===
  - Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego.
  - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n-1) + \lfloor \log(n) \rfloor</latex>
  - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(n/4) + T(3n/4) + n</latex>
  - Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne: \\ <latex>T(n) = T(\lfloor\sqrt{n}\rfloor) + \lfloor\sqrt{n}\rfloor</latex>

=== Niejasności z zajęć ===
Metoda graficzna:
<code>
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      OD
</code>
  * i(n)=n
  * j(i)=n
  * T(n)=n^2

<code>
for(i=0;i<n;i++)
   for(j=0;j<n;j+=2)
      OD
</code>
  * i(n)=n
  * j(i)=n/2
  * T(n)=n^2/2

<code>
for(i=0;i<n;i+=2)
   for(j=0;j<i;j++)
      OD
</code>
  * i(n)=n/2
  * j(i)=i
  * T(n)=n^2/8


<code>
for(i=0;i<n;i+=2)
   for(j=i;j>=1;j/=2)
      OD
</code>
  * i(n)=n/2
  * j(i)=log i
  * T(n)=n/2(log(n/2) - 1)