Upozorňujeme, že diskuze pod našimi online kurzy jsou nemoderované a primárně slouží k získávání zpětné vazby pro budoucí vylepšení kurzů. Pro studenty našich rekvalifikačních kurzů nabízíme možnost přímého kontaktu s lektory a studijním referentem pro osobní konzultace a podporu v rámci jejich studia. Toto je exkluzivní služba, která zajišťuje kvalitní a cílenou pomoc v případě jakýchkoli dotazů nebo projektů.
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(n2)
Nemělo by to být naopak?
V praxi se ale samozřejmě může stát, že velmi špatně napsaný algoritmus s O(n2) 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!
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
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 = 4n2 + 3 =
O(n2)
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(n2) a nikoliv O(n).
Mohl by se na to někdo kompetetní podívat a případě opravit?
Děkuji.
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.
Zobrazeno 9 zpráv z 9.
