Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#2 17. 12. 2010 17:01
- Lumikodlak
- Místo: Praha
- Příspěvky: 212
- Pozice: Programator nebo tak neco :-)
- Reputace: 19
Re: Výpočet časové složitosti operace modulo.
Podle me je ta slozitost O(n).
Predpokladejme, ze to cislo kterym se deli, je male - dejme tomu B.
Na vstupu je nejake cislo A1 A2 ... An.
Zbytek po deleni se da spocitat takhle: (jestli se nepletu)
Nejdriv vydelis prvni dve cislice cislem B, a z nich mas zbytek po deleni treba X1: (A1 A2) mod B = X1
z cislic A1 a A2 tedy zbyde X1, takze mame:
X1 A3 A4 ... An
Dal vezmes zbytek po deleni: (X1 A3) mod b = X2
takze zbyde:
X2 A4 A5 ... An
spocitas zbytek po deleni (X2 A4) mod b = X3
atd...
Takze po n-1 krocich ziskas Xn-1 coz by mel byt vysledny zbytek po deleni.
Kdyby B bylo take velke, tak jednotlive kroky budou slozitejsi, ale celkovy pocet operaci vzhledem k cisle na vstupu bude zase O(n). V zadani je psano, ze to ma byt slozitost vzhledem k delce vstupu a tim vstupem, predpokladam, je myslen jen ten delenec, takze jsem tu delku delitele nezapocitaval.
(doufam, ze me nekdo opravi kdyztak :-) protoze touto oblasti jsem se nikdy moc nezabyval)
Offline