obraz4 (50)

Złożoność obliczeniowa - przykład rozw. II

Można zauważyć, że dodawane elementy w każdym wierszu są sumą kolejnych wyrazów ciągu arytmetycznego:

function suma(n: integer): integer; var i, s: integer; beg i n

s := 0;

for i := 1 to n do

s + i * (i + 1)/2;

s := s + i * (i + 1)/2;

return s;

7/

end;

liczba dodawań s := s + i * (i + 1)/2;

Wykład 5 Pi cia aniowaiiie komputerów I 23