Matematické Fórum

Google · 13. 04. 2016 15:45

Dobrý den,
studuju na test z informatiky, téma výpočetní složitost algoritmů, potřeboval bych poradit, protože tomu, co je v učebnici nechápu. Jedná se o takový řešený příklad:

Stanovte výpočetní složitost polynomu $p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$ , kde $a_{n}$ je různé od 0.

Ten postup obecně chápu. Stanovím složitosti pro násobení a sčítání a tyto hodnoty potom porovnám a výpočetní složitost polynomu je ta větší z hodnot. Co ale NECHÁPU je stanovení výpočetní složitosti pro ten počet násobení v polynomu:
$n+(n-1)+\ldots +2+1=n\cdot \frac{n+1}{2}$ → tohle v pohodě chápu, tahle matika mi jde
ale potom $n\cdot \frac{n+1}{2}=\frac{n^{2}}{2}+\frac{n}{2}=O(n^{2})$ → tak tohle NECHÁPU. Sice znám tu podmínku, že musí být splněno $f(n)\le c\cdot g(n)$ , ale PROČ TO TEDA TŘEBA NEMŮŽE BÝT $n\cdot \frac{n+1}{2}=O(\frac{n^{2}}{2}+n)$ ???

Děkuji pěkně

jarrro · 13. 04. 2016 16:08 — Editoval jarrro (13. 04. 2016 16:08)

$O{$\frac{n^{2}}{2}+n$}=O{$n^2$}$

Google · 13. 04. 2016 16:14

↑ jarrro: aha ok :D díky

Matematické Fórum

#1 13. 04. 2016 15:45

Stanovení výpočetní složtosti

#2 13. 04. 2016 16:08 — Editoval jarrro (13. 04. 2016 16:08)

Re: Stanovení výpočetní složtosti

#3 13. 04. 2016 16:14

Re: Stanovení výpočetní složtosti

Zápatí