PHP týden Předvánoční slevová akce
Další šance dokončit svůj projekt a získat ceny v hodnotě 10.000 Kč! Pokračování úspěšné letní soutěže - ITnetwork winter
Využij předvánočních slev a získej od nás 20 % bodů navíc zdarma! Zároveň také probíhá PHP týden se slevou na e-learning až 80 %

Lekce 3 - Časové složitosti algoritmů a triky pro její odhad

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

V minulé lekci, Výpočet časové složitosti algoritmu, jsme celkem puntičkářsky počítali, jak je přesně algoritmus složitý. V praxi se ale setkáme s takovým množstvím různých úloh, že by bylo velmi těžké přesně určit všechny kroky, abychom spočítali složitost daného algoritmu. V dnešní lekci si ukážeme pokročilejší práci s kombinováním algoritmů a začneme si představovat složitostní třídy podobných úloh. V těch budeme pokračovat i příště a nakonec si i zkusíme několik algoritmů analyzovat a jejich složitost určit, tentokrát již bez procházejí každého kroku! :)

Tento článek je trochu náročnější a doporučuji si předem prolistovat články o řadících algoritmech a datových strukturách. Nebo vás naopak článek navnadí a s chutí si je přečtete po článku... :)

Mozek

Konstantní časová složitost

Toto je taková "nirvána" programátorů. Něco, co i na obrovských datech trvá okamžik.

Buddha

Zářným příkladem je hledání minima/maxima na haldě. Vzhledem k tomu, že si halda udržuje vždy informaci o tom, kde má minimum, tak i při 101000 číslech v haldě najdeme minimum okamžitě.

Konstantní časová složitost tedy označuje, že čas potřebný k provedení daného úkonu vůbec nesouvisí s počtem prvků n, se kterými pracujeme.

Konstantní časová složitost ovšem není až tak zajímavá z programátorského hlediska, protože přichází jen s určitými datovými strukturami a na omezené typy úloh.

Konstantní složitost mají např. následující operace:


 

...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 této lekci se blíže podíváme na různé třídy algoritmů a toho, zda máme nějaké triky, jak určit složitost jednotlivých algoritmů

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
Výpočet časové složitosti algoritmu
Všechny články v sekci
Úvod do teorie algoritmů
Miniatura
Následující článek
Časové složitosti algoritmů a příklady odhadu složitosti
Aktivity (3)