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 si začali představovat ty nejzákladnější katerie algoritmů a jejich asymptotickou časovou složitost. V dnešní lekci budeme pokračovat a na závěr 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...

Prémiový článek

Prémiový článek

Na itnetwork.cz se nachází největší a nejucelenější česká databáze s výukovými články, jejímž cílem je umožnit kvalitní vzdělání v oblasti IT úplně každému. Měsíčně zobrazíme k milionu článků a sklidíme desítky děkovných emailů, kde nám sdělujete, že jsme vám pomohli k lepšímu zaměstnání nebo vzdělání.

Ačkoli se snažíme držet většinu obsahu úplně zadarmo, udržovat síť v provozu a aktuální stojí obrovské úsilí. Proto je nějaký obsah, jako cvičení nebo odbornějšíčlánky, přístupný pouze za body. Nebojte, nestojí to skoro nic :)

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.

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

Koupit články a funkce postupně a po jednom 20 bodů
Koupit celý kurz se všemi články a funkcemi za exkluzivní cenu 17 bodů
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 4 článkům s kontrolou a certifikací a ještě navíc ušetříš 8 Kč. Nabídka je omezená pouze pro první články z kurzu a obsahuje exkluzivní slevu 15%.
17 bodů získáš za přidání svého článku na síť nebo odpovídá 50 Kč 43 Kč

Koupit pouze tento článek

Pozor, pokud si koupíš pouze tento článek, ztratíš nárok na speciální slevu 15% na balíček všech článků.

Pro přístup k článku potřebuješ 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č

Koupí článku k němu získáš neomezený přístup a to napořád. Posuneš své znalosti zas kousek dopředu a zároveň nám pomůžeš udržovat celý projekt při životě a pomáhat vám tak k lepší budoucnosti.

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

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íť.

Dobít body můžeš okamžitě např.:

Kartou SMS Převodem
Kartou SMS Převodem

 

Článek pro vás napsal Tricerator
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.
Předchozí článek
Časové složitosti algoritmů a triky pro její odhad
Všechny články v sekci
Úvod do teorie algoritmů
Aktivity (2)