ALG5

3.4. Przykład 3: Wpadamy w pułapkę 65

7\«)-/_t(l + N + Nt[i]).

T{n) ~ max(A\ AV[/]).

Początek jest klasyczny: „zewnętrzna” suma od 1 do N z równania (*) zostaje zamieniona na A-krotny iloczyn swojego argumentu. Podobny „trik” zostaje wykonany w równaniu (**), po czym możemy już spokojnie zająć się grupowaniem i upraszczaniem... Czas wykonania programu jest proporcjonalny do większej z liczb: N i A7[i] i tylko tyle możemy na razie stwierdzić. Niestety, kończąc w tyin miejscu rozważania wpadlibyśmy w pułapkę. Naszym problemem jest bowiem nieznajomość zawartości tablicy, a ta jest potrzebna do otrzymania ostatecznego wyniku! Nie możemy przecież zastosować funkcji matematycznej do wartości nieokreślonej.

Nasze obliczenia doprowadziły zatem do momentu, w którym zauważamy brak pełnej informacji o rozważanym problemie. Gdybyśmy przykładowo wiedzieli, że w tym fragmencie programu, w którym „pracuje” nasza funkcja, można z dużym prawdopodobieństwem powiedzieć, iż tablica wypełniona jest głównie zerami, to nie byłoby w ogóle problemu! Nie mamy jednak żadnej pewności, czy rzeczywiście zajdzie taka sytuacja. Jedynym rozwiązaniem wydaje się zwrócenie do jakiegoś matematyka, aby len, po przyjęciu dużej ilości założeń, przeprowadził analizę statystyczną zadania i doprowadzi! do ostatecznego wyniku w satysfakcjonującej nas postaci.

3.5. Przykład 4: Różne typy złożoności obliczeniowej

Postawmy ponownie przed sobą następujące zadanie: należy sprawdzić, czy pewna liczba ,v znajduje się w tablicy o rozmiarze n Zostało już ono rozwiązane w rozdziale 2, spróbujmy teraz napisać iteracyjną wersję tej samej procedury. Nie jest to czynność szczególnie skomplikowana i sprowadza się do ułożenia następującego programu:

szukaj, cpp

const n=10;

int tab[n]=(l,2,3,2,-7,44,5,l,0,-3l; int szukaj(int tab[n|,int x)

{// funkcja zwraca indeks poszukiwanego elementu x int pos=0;

whilc ((pos<n) &£ (tab[pos]!=x)) pos++;

if(pos<n)