Termin zajęć: 29/30.03.2011

Do przygotowania:

1. Znajomość i rozumienie pojęć:
   1. Złożoność obliczeniowa.
   2. Złożoność pamięciowa:
      1. Działanie algorytmów „w miejscu”.
   3. Złożoność pesymistyczna.
   4. Złożoność oczekiwana.
   5. Złożoność optymistyczna.

Zajęcia odbywać się będą głownie przy tablicy. Nie ma konieczności przynoszenia laptopów.

Umożliwia szybkie wyznaczanie rozwiązania równania rekurencyjnego postaci:
gdzie:

• a ≥ 1
• b > 1
• f(n) jest funkcją asymptotycznie dodatnią.
• iloraz interpretujemy jako lub jako

Wtedy T(n) może być ograniczona asymptotycznie w następujący sposób:

1. Jeżeli dla pewnej stałej ε > 0 to,
2. Jeśli to,
3. Jeżeli dla pewnej stałej ε > 0 oraz dla pewnej stałej c i wszystkich dostatecznie dużych n, to

1. Metodą reukrencji uniwersalnej wyznacz złożoność obliczeniową algorytmu wyszukiwania binarnego.
2. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
   
3. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
   
4. Rozwiąż w sensie asymptotycznym następujące równanie rekurencyjne:
   

Metoda graficzna:

for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      OD

• i(n)=n
• j(i)=n
• T(n)=n^2

for(i=0;i<n;i++)
   for(j=0;j<n;j+=2)
      OD

• i(n)=n
• j(i)=n/2
• T(n)=n^2/2

for(i=0;i<n;i+=2)
   for(j=0;j<i;j++)
      OD

• i(n)=n/2
• j(i)=i
• T(n)=n^2/8

for(i=0;i<n;i+=2)
   for(j=i;j>=1;j/=2)
      OD

• i(n)=n/2
• j(i)=log i
• T(n)=n/2(log(n/2) - 1)