Archiv diskusního fóra o matematice, 2006–2026
Stránky: 1

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.
Offline

Aby téma nezůstalo bez odpovědi, je možno dodat, že se uvedené skutečnosti nezmění, ani když urychlíme násobení použitím Karatsubova, Montgomeryho nebo Toom-Cookova algoritmu.
Offline
Stránky: 1