Mikuláš je tu! Získaj 90 % extra kreditov ZADARMO s promo kódom CERTIK90 pri nákupe od 1 199 kreditov. Len do nedele 7. 12. 2025! Zisti viac:
NOVINKA: Najžiadanejšie rekvalifikačné kurzy teraz s 50% zľavou + kurz AI ZADARMO. Nečakaj, táto ponuka dlho nevydrží! Zisti viac:

Diskusia – 1. diel - Úvod do teórie algoritmov

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
Posledné komentáre sú na spodnej časti poslednej stránky.
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.

Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovedá 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.

Avatar
michaelp
Člen
Avatar
Odpovedá 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.

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.

Odpovedať
the cake is a lie
Avatar
Luboš Běhounek Satik
Tvůrce
Avatar
Odpovedá na Petr Čech
Luboš Běhounek Satik:3.4.2015 10:15

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

Odpovedať
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?

Avatar
Martin Dráb
Tvůrce
Avatar
Odpovedá 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.

Odpovedať
2 + 2 = 5 for extremely large values of 2
Avatar
Lukáš Hruda
Tvůrce
Avatar
Odpovedá 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á.

Avatar
Martin Dráb
Tvůrce
Avatar
Odpovedá 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žší.

Odpovedať
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 :)

Posledné komentáre sú na spodnej časti poslednej stránky.
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é 10 správy z 35.