7. úloha

[roman_]

Moja otázka znie: keď mám v pamäti uložené intervaly čísel tak, že týchto intervalov je vždy konštantný počet (ktorý by bol väčší, keby boli na vstupe povolené aj väčšie čísla (teda závisí od max. veľkosti čísla na vstupe)), môžem považovať pamätovú zložitosť za konštantnú? a časovú zložitosť prejdenia tohoto poľa môžem tiež považovať za konštantnú?

[USAmec]

No odpovedal si si sam, ze ta zlozitost zavisi od max. velkost vstupu a v zavislosti od nej by sa to patrilo vyjadrit

[roman_]

diky za odpoved... v tom pripade sa vynoruje dalsia otazka:
viem spravit program v casovej zlozitosti O(N log log M) a pamatovej
O (log M), alebo program v casovej zlozitosti O(N log M) a pamatovej O(1). N je pocet cisel na vstupe a M je najvacsie mozne cislo na vstupe.. ktory z nich je lepsi? prvy ma lepsiu casovu zlozitost, druhy ma lepsiu pamatovu zlozitost, momentalne mam odovzdany program s horsou casovou a horsou pamatovou, takze obidva to zvladnu na 7

[USAmec]

povedal by som, ze je to asi uplne jedno.

[Baklažán]

Mám považovať časovú zložitosť načítania čísla za konštantnú? Lebo podľa mňa je logaritmická (od veľkosti čísla), čo by zároveň riešilo Romanovu otázku.

[USAmec]

povedzme, ze je to pre jednoduchost a nezblaznenie sa konstanta

(inac baklazan ma pravdu, keby M bolo uz fakt velke, tak by bolo dobre uvazovat o tom, ze ma lg M cifier a podla toho trvaju operacie s nim)