obraz8 (44)

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

Należy zwrócić uwagę na dodatkowe warunki zmieniające ilość wykonania pętli. Przykładowo jaka będzie złożoność czasowa następującego fragmentu programu:

m:=1    int m = 1;

for i1:= 0 to n if i1 = m then begin

m:= m * (n - 1): for i2:= 0 to n

0(1);

end;

for( int il = 0; il < n; il++ ) if( il == m ){ m *= (n - 1) ;

for ( int i2 = 0; i2 < n; i2++ ) {

0(1) ;

}

}

czas wykonania jest liniowy (a nie kwadratowy lub logarytmiczny) bo: przy n > 3 pętla wewnętrzna wykonywana jest tylko dwa razy dla i1 = 1 oraz ii = n -1

Wykład f Programowanie komputerów I