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 25. 12. 2014 11:11
Analýza algoritmu
Ahoj,
dělám na jednom projektu do školy a vymyslel jsem si svůj vyhledávací algoritmus - hledá slova v nějaké mapě a vyplivne - TRUE, FALSE (našel/nenašel).
Chtěl bych ho analyzovat a napsat něco o něm, například porovnat rychlost běhu s hledáním v poli atd...
Máte nějaké nápady jak by to šlo udělat? Analyzovat? Co všechno bych do toho mohl zahrnout? Rychlost/paměť...?
Díky za rady a nápady.
Má kouzelná buřinka asi nefunguje.... Jinak bych tu nebyl...
Reputace slušností...
Předem všem děkuji za Vaše rady..
Offline
#2 02. 01. 2015 20:58
Re: Analýza algoritmu
Ahoj,
určitě bych zkusil analyzovat čas běhu - (asymptotickou složitost, viz. https://cs.wikipedia.org/wiki/Asymptoti … C5%BEitost) a i náročnost na paměť (o kolik víc než je velikost vstupu, tj. Tvá mapa, si algoritmus alokuje). Pro srovnání se můžeš podívat na https://cs.wikipedia.org/wiki/%C5%98adi … _algoritmy
Offline
#3 10. 01. 2015 10:05
Re: Analýza algoritmu
↑ mb305:
Ahoj, díky, přemýšlel jsem také o asymptotické složitosti, ale jak jí určím, pokud se kód skládá z 5 metod a každá ta metoda má for, či porovnání stringů?
Má kouzelná buřinka asi nefunguje.... Jinak bych tu nebyl...
Reputace slušností...
Předem všem děkuji za Vaše rady..
Offline
#4 11. 01. 2015 15:10
Re: Analýza algoritmu
↑ PanTau:
Ahoj,
1/ Porovnání stringů - jedná se opět o nějakou sadu operací (buď v metodě, nebo třeba implementované v samotném jazyku). Tudíž se dá vyčíslit (asymptoticky to bude nejjednodušší). Mělo by stačit se podívat do implementace metody / jazyka - z toho by mělo jít složitost najít.
2/ Složení z 5-ti metod - to nevadí. Buď můžeš kód přepsat do jedné metody (pouze pro vyčíslení, z pohledu softwarového inženýrství je to velký prohřešek) a nebo (což bych volil já) si spočítat složitosti jednotlivých metod a pak se sečíst / násobit podle toho jestli jsou sekvenčně za sebou, nebo zda jsou vnořené. U tohoto bude ale potřeba si dát pozor na to, že do jednotlivých metod nemusí vstupovat celý vstup pro základní výpočet. (příklad: do algoritmu vstupuje celý článek v HTML, ale do dílčí metody vstupují pouze části s tagy IMG)
Offline
#5 12. 01. 2015 13:21
Re: Analýza algoritmu
↑ mb305:
Ahoj, o asymptotické složitosti jsem se učil před rokem, v té době jsem ji ani přes velkou snahu moc nepochopil, myslíš, že by jsi mi s tím mohl trochu pomoci?
Jinak děkuji za odpověď.
Má kouzelná buřinka asi nefunguje.... Jinak bych tu nebyl...
Reputace slušností...
Předem všem děkuji za Vaše rady..
Offline
#6 13. 01. 2015 09:54
Re: Analýza algoritmu
↑ PanTau:
Rád se o to alespoň pokusím. Napřed se podívej na https://edux.fit.cvut.cz/oppa/BI-ZDM/pr … M-P01.pdf. Na slajdu 20 je formální definice. Poté sem zkus dát kód (jeho část, popř. i technologie na kterých pracuješ - jazyky, knihovny) a zkusíme se na ni společně podívat.
Offline