KSP.sk

Korešpondenčný seminár z programovania


Odpovedať 
 
Hodnotenie témy:
  • 0 Hlasov - 0 Priemer
  • 1
  • 2
  • 3
  • 4
  • 5
7. úloha
06.01.2012, 17:27:07
Príspevok: #1
7. úloha
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ú?
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
06.01.2012, 17:29:02
Príspevok: #2
RE: 7. úloha
No odpovedal si si sam, ze ta zlozitost zavisi od max. velkost vstupu a v zavislosti od nej by sa to patrilo vyjadrit Icon_smile
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
06.01.2012, 17:53:10
Príspevok: #3
RE: 7. úloha
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? Icon_cheesygrin 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
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
06.01.2012, 18:01:42
Príspevok: #4
RE: 7. úloha
povedal by som, ze je to asi uplne jedno.
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
09.01.2012, 20:25:04
Príspevok: #5
RE: 7. úloha
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.
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
09.01.2012, 21:29:19
Príspevok: #6
RE: 7. úloha
povedzme, ze je to pre jednoduchost a nezblaznenie sa konstanta Icon_smile

(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)
Vyhľadať všetky príspevky tohoto používateľa
Citovať príspevok v odpovedi
Odpovedať 







Účet

Ako sa prihlásim?
 
loading

Redirecting