ALG7

3.1. Dobre samopoczucie użytkownika programu 57

mów zostaną wprowadzone na reprezentatywnych przykładach, co wydaje się lepszym rozwiązaniem niż zacytowanie suchych definicji.

3.2. Przykład 1: Jeszcze raz funkcja silnia...

Do zdumiewających zalet funkcji silnia należy niewątpliwie mnogość zagadnień, które można za jej pomocą zilustrować... Z rozdziału poprzedniego pamiętamy jeszcze zapewne rekurencyjną definicję:

0! = 1,

«!=«*(« — 1)! gdzie n > 1

Odpowiadająca tej formule funkcja w C++ miała następującą postać:

int silnia(int n)

{

if (n—0) return 1; olso

return n* silnia(n-1);

)

Przyjmijmy dla uproszczenia założenie, bardzo zresztą charakterystyczne w tego typu zadaniach, że najbardziej czasochłonną operacją jest tutaj instrukcja porównania if. Przy takim założeniu czas. w jakim wykona się program, możemy zapisać również w postaci rekurencyjnej:

T(0) = t_c,

T{n) = l_c + T(n -1 )dla n > 1.

Powyższe wzory należy odczytać w sposób następujący: dla danej wejściowej równej zero czas wykonania funkcji, oznaczany jako T(0), równa się czasowi wykonania jednej instrukcji porównania, oznaczonej symbolicznie przez t_c. Analogiczny czas dla danych wejściowych > 1 jest równy, zgodnie z formułą rekurencyjną, T(n)~t_c+T(n~J).

Niestety, tego typu zapis jest nam do niczego nieprzydatny - trudno np. powiedzieć od razu, ile czasu zajmie obliczenie silnia(lOO)... Widać już, że do problemu należy podejść nieco inaczej. Zastanówmy się, jak z tego układu wyliczyć T(n), tak aby otrzymać jakąś funkcję nierektirencyjną pokazującą, jak czas wy-