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( 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

Wyszukiwarka

Podobne podstrony:
0000001 44 94 Fizjoterapia w diirurg i 1 ......... należy zwrócić uwagę na ćwiczenia zwiększające ru
obraz7 (47) Złożoność obliczeniowa - przykład Jeśli zmienna sterującą nie zmienia się liniowo należ
obraz9 (44) Złożoność obliczeniowa - inny przykład Jaka będzie złożoność poniższego fragmentu? fo
obraz0 (62) Złożoność obliczeniowa - przykład procedurę zagadka(n integer); var i. k. 1: integer; b
obraz2 (59) Złożoność obliczeniowa - przykładAlgorytm obliczający sumę elementów leżących na i poni

więcej podobnych podstron