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

Späť

Upozorňujeme, že diskusie pod našimi online kurzami sú nemoderované a primárne slúžia na získavanie spätnej väzby pre budúce vylepšenie kurzov. Pre študentov našich rekvalifikačných kurzov ponúkame možnosť priameho kontaktu s lektormi a študijným referentom pre osobné konzultácie a podporu v rámci ich štúdia. Toto je exkluzívna služba, ktorá zaisťuje kvalitnú a cielenú pomoc v prípade akýchkoľvek otázok alebo projektov.

Komentáre

krepsy3

Tvůrce

krepsy3:6.2.2019 17:22

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"

Odpovedať

Programátor je stroj k převodu kávy na kód.

Ondřej Michálek

Tvůrce

Ondřej Michálek:8.2.2019 18:49

Opraveno, díky

Odpovedať

Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...

asifa.hvshthvg

Člen

asifa.hvshthvg:31.12.2019 10:28

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)

Odpovedať

Ondřej Michálek

Tvůrce

Ondřej Michálek:31.12.2019 10:59

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!

Odpovedať

Raduj se z bugu. Tedy z toho, ktery jsi uz nasel...

Martina MAKOVSKÁ

Člen

Martina MAKOVSKÁ:7.9.2023 10:28

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

Odpovedať

nrgpostsk

Člen

nrgpostsk:8.10.2023 15:35

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.

Odpovedať

Ivo Fořt

Člen

Ivo Fořt:5.5.2024 10:21

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

Odpovedať

Vítězslav

Člen

Vítězslav:9. októbra 8:47

Ahoj,

Ať se dívám, jak se dívám, tak nikde žádnou složitost
1 + n * ( n + n + n + n + 0 ) + 1 + 1 = 4n² + 3 = O(n²)
u algoritmu "Naivní prohledávání pole" nevidím. Pořád je to O(n).

Naopak algoritmus "Ultrahloupé prohledání pole" je podle mého názoru O(n²) a nikoliv O(n).
Mohl by se na to někdo kompetetní podívat a případě opravit?
Děkuji.

Odpovedať

DarkCoder

Člen

DarkCoder:9. októbra 14:59

Naprosto správná úvaha.

Kód naivního algoritmu pro hledání maxima nedělá to co se očekává. Pouze zpomaluje tím, že při nalezení maxima se testovaný prvek otestuje 2x. Ale pořád se jedná o časovou složitost O(n). pouze s tím že každý prvek se v nejhorším případě (vzestupné pole) otestuje 2x.

Ultrahloupý algoritmus má také složitost O(n), avšak počet operací je n * 1000 001.

Kvadratická složitost O(n²) by nastala například tehdy, kdybychom při každém nalezení nového maxima:

znovu prošli celé pole od začátku

nebo

porovnávali každý prvek se všemi ostatními

Ale to se v tomto algoritmu neděje. continue jen zdržuje o jedno porovnání navíc, ne o celý nový průchod polem.

Editované

Odpovedať

"I ta nejlepší poučka postrádá na významu, není-li patřičně předána." - DarkCoder

Robíme čo je v našich silách, aby bola tunajšia diskusia čo najkvalitnejšia. Preto do nej tiež môžu prispievať len registrovaní členovia. Pre zapojenie sa do diskusie sa zaloguj. Ak ešte nemáš účet, zaregistruj sa, je to zadarmo.

Zobrazené 9 správy z 9.

Najčastejšie vyhľadávané

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