zložitosť algoritmov príklad
Viete mi, prosím, pomôcť s týmto?
Odpovědi
Diskuze
(n+1) + (n) + (n-1) + (n-2) + ... + (2) + (1) + (0) =
...
Jsou to jednoduché součty úměrné velikosti n.
Když se ta suma počítá po členech, tak délka výpočtu závisí na velikosti n, tedy O(n). Když se ta suma ale počítá přes souhrnný vzorec (viz níže), tak doba výpočtu nezáleží na n. Jsou to vždy jen 2 součty a 2 násobení a složitost je tak konstantní: O(1)
-------------------------------------
1.suma = aritm.posloupnost:
m (počet členů) = n+2
a1 = n-0+1
d = -1
am = n-n-1+1 = 0
s_(m+2) = m/2.(a1 + am)
s_(m+2) = (n+2)/2 . (n+1 + 0)
s_(m+2) = (1/2).(n+2).(n+1)