obraz
9 (65)

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

,    ,, .    . . instrukcje w pętli while wykonują

¹    ^ sie az nastapi warunek I >= n

var i. k. 1: integer:

hesin    P° j-tym wykonaniu pętli while

for i = 1 to n² do    wartość zmiennej k wynosi 2j + 1,

begin

k := 1; 1 := 1:

while I n do begin

k k +2:1 := 1 + k;

end

end

end:

zaś zmienna I równa sie 1 +3 + 5 + ... + (2j +1) = j(j + 1) + j + 1 =(j

+ 1)².

Liczba wykonań pętli while = najmniejsze j takie że (j + 1 )² >= n czyli

j= : \n i -1 całkowita liczba wykonań instrukcji podstawowej =

n² <r\nl -1) czyli algorytm jest klasy 0(n^5/2)

Wvklad 5 Programowanie komputerów I 18