Lekce 4 - Časová složitost algoritmů a jejich odhad složitosti
V minulé lekci, Třídy časové složitosti algoritmů a jejich využití, jsme se podívali na různé třídy časové složitosti algoritmů, jejich využití a určení složitosti jednotlivých algoritmů.
V dnešním tutoriálu o teorii algoritmů se blíže podíváme na časovou složitost algoritmů a naučíme se odhadnout jejich složitost.
Ukážeme si, jak funguje faktoriálová časová složitost, dále také časová složitost grafových algoritmů, a také zkusíme odhadnout časovou složitost dvou příkladů konkrétního algoritmu.
Faktoriálová časová složitost
Pokud si vzpomeneme na kombinatoriku z hodin matematiky, tak nás může napadnout, že faktoriál bude souviset s vyzkoušením úplně všech možností.
Pro n = 1 je to 1 operace. Pro n = 5
je to již ale 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í. Většinou se
k těmto číslům dostaneme tak, že zkoušíme všechny možnosti. Proto se
tedy snažíme vyvarovat této časové složitosti.
Pro problém setřídění pole si můžeme představit, že by program místo nějakých smysluplných operací zkoušel čísla různě prohazovat do vyčerpání všech kombinací. Některá z kombinací by splňovala podmínku setříděného pole.
Faktoriálovou složitost, O(n!), bychom dostali, pokud
bychom
...konec náhledu článku...
Pokračuj dál
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.
Koupit tento kurz
Před koupí tohoto článku je třeba koupit předchozí díl
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- 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 tutoriálu o teorii algoritmů se blíže podíváme na časovou složitost algoritmů a naučíme se odhadnout jejich složitost.
Kredity 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íť.
