obraz7 (47)

Złożoność obliczeniowa - przykład

Jeśli zmienna sterującą nie zmienia się liniowo należy szacować czas wykonania również w nie-liniowy sposób. W szczególności wykładnicza zmiana zmiennej sterującej pętlą pociąga logarytmiczny czas wykonania:

while i < n do begin

i:= i * k;

0(1);

k~-' < n < k^m

a wiec

C

int i = 1; while( i < n )

{

i *= k; 0(1) ;

} m -1 < log_k n < m, oraz T(n) * c log_k a

26

W\idad 5    Progr amowanie komputerów I

„    i