Pseudopolynomiální algoritmy

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:
BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí
Přehled tématu
   

Rozšířit náhled Přehled tématu: Pseudopolynomiální algoritmy

Re: Pseudopolynomiální algoritmy

od HonzaK » 28. 1. 2012 16:24

Protoze pri unarnim kodovani je pro zapis cisla potreba udelat tolik "carek", kolik je to cislo, kdyzto pri binarnim a vyssim kodovani staci O(log(b)) bitu pro zapsani cisla b. Kdyz to tedy vezmes z opacne strany, tak pri unarnim zapisu se treba velikost toho b da omezit nejakym polynomem v promenne kod(X) (jak je to definovano ve slajdech dale), tedy plati b <= p(kod(X)) (p je ten polynom). Pri binarnim kodovani ale roste max. hodnota b exponencialne vzhledem k poctu bitu, ktere pouzijes na jeho zapis, nemuzes tedy velikost b omezit nejakym polynomem.

Pseudopolynomiální algoritmy

od jamos » 28. 1. 2012 14:39

Zdravím,

ve slajdech ze složitosti 1, je těsně před kapitolou o pseudopolynomiálních algoritmech uveden algoritmus pro součet podmnožiny. Je u něj uvedená složitost O(nb). Mohl by mi prosím někdo vysvětlit proč je tato složitost exponenciální vzhledem k binárnímu kódování a polynomiální vzhledem k unárnímu?

Díky.

Nahoru