ALG4

64 Rozdział 3. Analiza sprawności algorytmów

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

Zadania z dwóch poprzednich przykładów charakteryzowała istotna cecha: czas wykonania programu nie zależał od wartości, jakie przybierała dana, lecz tylko od jej rozmiaru. Niestety nie zawsze tak jest! Takiemu właśnie przypadkowi poświęcone jest kolejne zadanie obliczeniowe. Jest to fragment większego programu. którego rola nie jest dla nas istotna w tym miejscu. Załóżmy, że otrzymujemy ten „wyrwany z kontekstu” fragment kodu i musimy się zająć jego analizą:

const N-1G; int t(NJ;

funkcja_ad_hoc() i

int k, i;

// C_a // t_c

int suna=0; while (i<N)

{

U tc

U ta

// ta

while (j<-t[i]) (

s uma = suna-2;

3-3*i;

i^i+1;    II ta

I

)

Uprośćmy nieco problem zakładając, że:

•    najbardziej czasochłonne są instrukcje porównania, wszelkie inne ignorujemy zaś jako nie mające większego wpływu na czas wykonania programu.

•    zamiast pisać explicite t_c wprowadzimy pojęcie czasu jednostkowego wykonania instrukcji, oznaczając go przez 7.

Niestety jedno zasadnicze utrudnienie pozostanie aktualne: nie znamy zawartości tablicy, a zatem nie wiemy, ile razy wykona się wewnętrzna pętla while\ Popatrzmy, jak możemy sobie poradzimy w tym przypadku:

N (

n

T(n) = t_c + Nl_c +    ,