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

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

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...
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 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ů

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)