obraz1 (61)

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

Instrukcja zawarta w najbardziej wewnętrznej pętli wykonuje się j razy.

Pojedyncze wykonanie pętli 1 (czyli pętla 2) wykona

sie:

n

;=i⁺i

¹    i 1 ,    ,    1    ,    1

; = — n\;?+11—7i7 + l| =— — +(77-71

~>

Łączna liczba wykonania instrukcji z linii 4 wynosi

n-1 n

n-l

=1 =1-1 <=1

«_L2

1,1,

—r + — (;? — /

?    9

— 77”(77 — 1) — — * — (77 — 1 )

9    9    9

/

77 -

O

/

1 2—. ,    1 U

1 ^

^    ^?--^9 /" H^ i

- i=i    2 _J=1    2 _;=1

11, IV ¹    3    1

77 + — • — (77 - 1 >77 = - 77 - -9    9

77

Wvfcład 5 Programowanie komputerów I 20