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
#1 18. 10. 2016 22:10
Časová složitost
Dobrý den,
potřebovala bych poradit s vytvářením algoritmu pro časovou složitost, konkrétně pro dělení čísel.
Mám číslo N a dělím ho číslem M. Potřebuji zjistit, kolik místa potřebuji v počítači pro tento výpočet, když si zadám neznámou n = počet cifer v čísle N a neznámou m = počet cifer v čísle M.
Abych řekla pravdu, nejsem si jistá, jak si mám představit časovou složitost, takže uvítám jakoukoliv odpověď.
Přede moc děkuji za Vaše odpovědi.
Offline
#2 18. 10. 2016 22:29
- ViliX
- Host
Re: Časová složitost
Stručně řečeno časová složitost značí kolik základních výpočtů musí počítač udělat (relativně k velikosti vstupu) aby vrátil výsledek.
Pokud mám například:
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
nejakyPrikaz;
Tak časová náročnost je n^2, neboť pro n se provede n^2 výpočtů. Kdybych měl místo nejakyPrikaz třeba příkazy tři, stále by to bylo n^2, neboť konstanta 3*n^2 je zanedbatelná pro velká čísla n. Doporučuji si pročíst třeba http://algoritmy.eu/zga/casova-slozitost/, odborněji je to rozebráno zde https://cs.wikipedia.org/wiki/Asymptoti … C5%BEitost. Tvým úkolem je tedy zjistit kolik základních operací se při dělení provede v závislosti na velikosti vstupu (počet cifer čísla).