Pseudopolynomická časová složitost

Pseudopolynomická časová složitost je v teorii složitosti taková časová složitost, která je vzhledem k číselné hodnotě vstupu polynomická, ale fakticky se jedná vzhledem k velikosti vstupu o složitost exponenciální.

Klasickým příkladem jsou algoritmy řešící problémy z teorie čísel, například testy prvočíselnosti. Naivní implementace algoritmu zkusmého dělení se snaží zjistit, zda je zadané přirozené číslo n prvočíslem, tak, že postupně zkouší dělit n čísly \left\{2,3,\dots,n-1\right\}. +more Na to potřebuje n-2 operací dělení, zdálo by se tedy, že se jedná o lineární závislost na vstupu. Ovšem velikostí vstupu není hodnota čísla, ale kolik zabírá místa v paměti počítače, tedy kolik má číslic. Například Mersennovu prvočíslu 2^{31}-1 stačí k uložení v paměti počítače v obvyklém kódování jen 31 až 32 bitů, ale algoritmus zkusmého dělení by pro jeho prověření potřeboval přes dvě miliardy dělení. Obecně číslo n potřebuje k uložení řádově l=\log_2n bitů, zkusmé dělení tedy provede zhruba 2^l dělení, což je závislost zjevně exponenciální.

Naproti tomu skutečně polynomickým algoritmem je například sčítání dlouhých čísel, kde školský algoritmus postupuje zprava číslici po číslici (se započítáním přenosu) a jeho časová složitost je tedy lineárně závislá nikoliv na hodnotě čísla, ale na počtu jeho číslic.

Kategorie:Teorie složitosti