Aktuálně: Postihly zákazy tvou profesi? Poptávka po ajťácích prudce roste, využij slevové akce 50% výuky zdarma!
Pouze tento týden sleva až 80 % na e-learning týkající se Javy
Discount week - May - 50

Lekce 4 - Časové složitosti algoritmů a příklady odhadu složitosti

V minulé lekci, Časové složitosti algoritmů a triky pro její odhad, jsme se podívali na různé třídy algoritmů a toho, zda máme nějaké triky, jak určit složitost jednotlivých algoritmů.

V dnešní lekci si ukážeme několik příkladů, jak lze složitost u algoritmů jednoduše určit.

Faktoriálová časová složitost

A máme zde "overkill", nejhorší možný případ. Pokud si vzpomínáte na kombinatoriku z hodin matematiky, možná vás napadlo, že faktoriál bude souviset s vyzkoušením úplně všech možností. Jakmile tuto složitost někde uvidíte, utíkejte! Pro n = 1 je to 1 operace. Pro n = 5 je to ale již 720 operací. Pro n = 10, tedy např. pro pole o deseti prvcích, musíme provést 3628800 operací. A pro n = 15 je to 1307674368000 operací... Nechcete vědět, jaké číslo je to pro pole o tisíci prvcích :) Většinou se k těmto číslům dostaneme tak, že zkoušíme všechny možnosti.

Pro problém setřídění pole si můžete představit, že by program místo nějakých smysluplných operací zkoušet čísla různě prohazovat, až by vyčerpal všechny kombinace a některá z nich by splňovala podmínku, že je pole setříděné. Brrrr...

Faktoriálovou složitost, O(n!), bychom dostali, pokud bychom se pokoušeli např. o:


 

...konec náhledu článku...
Pokračuj dál

Znalosti v hodnotě stovek tisíc získáš za pár korun

Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 30 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 26 bodů (65 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 6 lekcím s kontrolou a certifikací a ještě navíc ušetříš 10 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
26 bodů získáš za přidání svého článku na síť nebo odpovídá 75 Kč 65 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • Neomezený a trvalý přístup k jednotlivým lekcím.
  • Kvalitní znalosti v oblasti IT.
  • Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.

Popis článku

Požadovaný článek má následující obsah:

V lekci dokončíme představení časových složitostí algoritmů faktoriální složitostí a složitostí pro algoritmy grafové. Odhadneme složitost na příkladech.

Body získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Článek pro vás napsal Ondřej Michálek
Avatar
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Aktivity (5)