Diskusia – 2. diel - Výpočet časovej zložitosti algoritmu

Ahoj, pěkný článek, dopodrobna prochází tematiku, neznalým (i neznalým limit) myslím moc hezky osvětlí, jak to s časovou složitostí je.

Pár chybiček:

• sekce c) - "ultrahlouLé prohledání"
• sekce c) - v pseudokódu chybí jedno "KONEC BLOKU" a řádek výše je indentován o jednu úroveň méně, než by měl být
• Poslední řádek před "Poznámka na závěr" - má být "ten asymptoticky "horší" algoritmus"

Opraveno, díky

Ahoj, v sekci b, malý chaos na závěr je věta

V praxi se ale samozřejmě může stát, že velmi špatně napsaný algoritmus s O(n) bude na daném stroji rychlejší, než ten s O(n²)

Nemělo by to být naopak?

V praxi se ale samozřejmě může stát, že velmi špatně napsaný algoritmus s O(n²) bude na daném stroji rychlejší, než ten s O(n)

Určitě mělo. Jinak se to běžně stává, že algoritmus v O(n), byť blbě napsaný, je rychlejší než ten s druhou mocninou. Opraveno, díky!

Je škoda, že nejdou algoritmy vyzkoušet. Jink velmi pěkné.

zase moje subjektivni hodnoceni. Moc omacky a malo vysvetleno. Pro matematika urcite skvele ale pro ostatni nejakou animaci ozivit a vysvetlit. ale i tak dekuju.

Ahoj, vysvětlení naivního algoritmu mi připadá nejasné

"Kdybychom v poli narazili na větší prvek, než je doposud známé maximum,
spustili bychom celý cyklus znovu"

Podle vašeho kódu se ale celý cyklus znovu nespustí, poze se zopakuje 2x iterace, ve které bylo nalezeno další maximum.

"Přiřazení max_value = numbers[i] se provede minimálně
0-krát, maximálně n-krát a provede se jen, pokud
je hodnota proměnné max_value větší než prvek. Příkaz
continue se provede minimálně 1-krát, maximálně
n-krát."

Příkaz continue se nachází ve stejném bloku jako přiřazení maximální hodnoty a provede se tudíž ve stejném počtu jako přiřazení, tzn. v nejlepším případě 0-krát, v nejhorším n-krát.

Jinak děkuji za lekci

Ivo