Matematické Fórum

Zlatohlavok · 23. 01. 2014 17:10

Ahojte, mám otázku ohladom MT.

Prečo tento príklad sa dá riešiť:

//forum.matweb.cz/upload3/img/2014-01/93252_Sn%25C3%25ADmka%2Bobrazovky%2B2014-01-23%2Bo%25C2%25A017.07.03.png

A tento nie:

Respektíve nemôže byt výsledok druhého taký istý ako výsleodk prvého:
$n\log_{}^{2}n$

V prvom sa násobí log n v druhom sa delí log n.

Ďakujem :)

Zlatohlavok · 24. 01. 2014 10:29

Vygooglil som tento príklad a normálne ho tam vyrátali, ale za to napísali, že rozdiel nie je polynomiálny, resp. riešenie nie je polynomialne. Viete mi povedať čo to znamená? Ako to rozpoznám?

//forum.matweb.cz/upload3/img/2014-01/55743_Sn%25C3%25ADmka%2Bobrazovky%2B2014-01-24%2Bo%25C2%25A010.27.04.png

Ďakujem

Brano · 25. 01. 2014 12:44

oni v podstate iba tvrdia, ze ziadny z pripadov MT tuto situaciu neriesi, lebo su tam iba tieto tri
(v najsilnejsej verzii co som nasiel)

1) $f(n)\in O(n^{\log_ba-\varepsilon})$ pre $\varepsilon>0$
2) $f(n)\in\Theta(n^{\log_ba}\log^kn)$ pre $k\ge 0$
3) $f(n)\in \Omega(n^{\log_ba+\varepsilon})$ pre $\varepsilon>0$

a funkcia $n^{\log_ba}\log^kn$ pre $k<0$ nepatri ani do jednej z tychto tried - teda ak by si to chcel nejak vyriesit, tak by si si musel detailne pozriet dokaz MT a zistit ci sa ta veta neda nejak zosilnit ...

Matematické Fórum

#1 23. 01. 2014 17:10

Master theorem

#2 24. 01. 2014 10:29

Re: Master theorem

#3 25. 01. 2014 12:44

Re: Master theorem

Zápatí