Matematické Fórum

Byl tu ve středoškolské sekci položen dotaz na složitost výpočtu faktoriálu, nicméně byl umístěn v navhodném tématu.
Pokud bychom číslo i faktoriál reprezentovali unárně, bude pro vstup délky n délka výstupu rovna n!, čas potřebný pouze k zapsání výsledku je alespoň faktoriální, horní odhad počtu operací je v O((n+2)!).

Pokud bychom zapisovat výstup binárně, vyjdeme ze Stirlingovy aproximace a dostaneme
ln(n!) je v O(n*ln(n))
pokud budeme binárně zapisovat i vstup, máme exponenciální paměťovou a proto i časovou složitost. Pokud budme vstup zapisovat unárně, je paměťová složitost polynomiální, časová také (provádíme n násobení dvou čísel, z nichž každé má dělku menší než n^2).

Existuje tedy interpretace, ve které je problém v P, v ostatních interpretacích je v EXPTIME.