NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze – Lekce 1 - Úvod do teorie algoritmů

Zpět

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ů.

Komentáře
Avatar
michaelp
Člen
Avatar
michaelp:2.4.2015 17:34

Možná by bylo dobré zmínit, že logaritmy v tabulkách jsou o základu 2 a proč to tak je.

 
Odpovědět
2.4.2015 17:34
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na michaelp
Lukáš Hruda:2.4.2015 22:36

Logaritmy mohou být o libovolném základu, protože při změně základu logaritmu se pouze celý logaritmus vynásobí nějakou konstantou a to na asymptotickou složitost nemá vliv.

 
Odpovědět
2.4.2015 22:36
Avatar
michaelp
Člen
Avatar
Odpovídá na Lukáš Hruda
michaelp:3.4.2015 8:56

S jiným základem mi ale nevycházely v první tabulce ty uváděné časy.

 
Odpovědět
3.4.2015 8:56
Avatar
Petr Čech
Tvůrce
Avatar
Petr Čech:3.4.2015 9:09

Když není uveden základ logaritmu, je snad o základu 10 (dekadický) a ne 2 o_O ... A potom to konstanta, kterou se to násobí je také logaritmus.

Odpovědět
3.4.2015 9:09
the cake is a lie
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovídá na Petr Čech
Luboš Běhounek Satik:3.4.2015 10:15

V IT se obvykle pro základ logaritmu považuje dvojka

Odpovědět
3.4.2015 10:15
https://www.facebook.com/peasantsandcastles/
Avatar
michaelp
Člen
Avatar
michaelp:3.4.2015 10:34

Když počítám s logaritmem o základu 10:
n log n = 10*log 10 = 10*1=10 = 0,01s (neodpovídá tabulce)
S logaritmem o základu 2:
n log n = 10*log 10 = 10*3,3 = 0,033s (odpovídá tabulce)
Jsem už moc dlouho ze školy, takže se omlouvám, že to nějak nechápu. Mohu požádat o polopatický výpočet, jak jste se jinak dostali pro např. 10 prvků k 0,03s u funkce O(n log n) v první tabulce?

 
Odpovědět
3.4.2015 10:34
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na michaelp
Martin Dráb:3.4.2015 10:46

Z definice notace O nepřímo plyne, že na základu logaritmu nezáleží (i když je v reálu roven dvojce). Pokud má nějaký algoritmus asymptotickou časovou složitost O (n log n), znamená to, že se při jeho provádění udělá cn(log n), kde c je nějaká konstanta (multiplikativní).

A jelikož platí, že log_a x = (log_b x / log_b a), kde b je libovolný platný základ logaritmu, dostáváme, že abychom převedli logaritmus z jednoho základu na druhý, stačí jej přenásobit konstantou (což se v případě O notace skryje v té konstantě c).

P.S.
Článek jsem nečetl a ani komentáře pod ním, takže jestli to tady už někde zaznělo, tak se omlouvám.

Odpovědět
3.4.2015 10:46
2 + 2 = 5 for extremely large values of 2
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovídá na michaelp
Lukáš Hruda:3.4.2015 12:36

Uvádění nějakých časů u debaty o složitosti je celkem scestné, jelikož časy nejsou změřené, ale spočítané. V praxi nezáleží jen na složitosti, ale také na režii, kdy pro malý počet vstupních hodnot může algoritmus s vyšší složitostí být rychlejší. Například při řazení 10 hodnot, bude výhodnější použít insert sort než merge sort i přes to, že insert sort má složitost O(n2) a merge sort O(n * log n). Navíc to, že algoritmus má nějakou složitost, neznamená, že vždy provede právě tolik operací, například insert sort může klidně skončit už po n operacích, v případě, že vstupní data, jsou již seřazená.

 
Odpovědět
3.4.2015 12:36
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Lukáš Hruda
Martin Dráb:3.4.2015 13:12

Přesně tak. Navíc také záleží, jak je daná implementace algoritmu optimalizovaná. Pak jsou ty konstanty (skryté O-notací) zase jiné.

Například pokud počítáš Levensteinovu vzdálenost dvou 32KB řetězců (tzn. počet operací přidej/uber/změň znak, který je třeba provést, aby se jeden z řetězců stal druhým), klasická implementace poběží třeba 1.7 sekundu, ale po použití vektorových instrukcí se můžeš dostat i na hodnoty 6x nižší.

Odpovědět
3.4.2015 13:12
2 + 2 = 5 for extremely large values of 2
Avatar
bem.jiri12
Člen
Avatar
bem.jiri12:1.6.2015 22:15

Výborná teorie o algoritmech, musel jsem se k této lekci vrátit a stála zato. Díky :)

 
Odpovědět
1.6.2015 22:15
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 34.