výpočtová zložitosť a porovnania
Čaute, viete mi prosím pomôcť toto vypočítať? Ďakujem každému za pomoc.
Odpovědi
Diskuze
Smyčka "i" proběhne n-krát.
V ní smyčka "j" proběhne také n-krát.
Celková výp.náročnost: n x n = n^2
Ta druhá smyčka jde jen od i+1 a ne od 0, takže počet kroků v cyklu "j" je:
i=0 j=1..n-1, tj. celkem n-1 kroků
i=1 j=2..n-1, tj. celkem n-2 kroků
i=2 j=3..n-1, tj. celkem n-3 kroků
...
i=n-2 j=n-1 .. n-1, , tj. celkem 1 krok
Kroků je dohromady: n-1, n-2, n-3, ..., 2, 1 což je aritm.posloupnost:
a1 = n-1
d = -1
a počtem členů n-1 (viz "i" cyklus jdoucí od 0 do n-2, což je (n-2)+1 = n-1 opakování [ta +1 je tam pro započítání té nuly (i=0)])
Součet této aritm.posloupnosti je:
s = (n-1)/2.[(n-1)+1]
s = n.(n-1)/2
s = (1/2).(n^2 - n)
Jde tedy o složitost typu O(n^2)
Snad to mám dobře. Raději se ještě s někým poraď.