Matematické Fórum

Archiv diskusního fóra o matematice, 2006–2026

Toto je archiv Matematického Fóra. Fórum je dostupné jen ke čtení. Můžete se ale zaregistrovat na náš Discord server.

#1 09. 06. 2009 01:17

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4247
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Složitost faktoriálu

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.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#2 16. 11. 2009 01:00

Kondr
Veterán
Místo: Linz, Österreich
Příspěvky: 4247
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
 

Re: Složitost faktoriálu

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.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

Archiv Matematického Fóra · stav k 30. 8. 2026 · 633 258 příspěvků v 108 818 tématech