V počítačové vědě platí základní rovnice: Program = Algoritmy + Datové struktury. Algoritmus definuje postup řešení problému, zatímco datová struktura určuje, jakým způsobem budou data uložena v paměti pro co nejefektivnější přístup.
Volba správné struktury může zrychlit program tisícinásobně. Rozdělujeme je na základní (lineární) a pokročilé (nelineární).
* Pole (Array): Kolekce prvků stejného typu uložených v souvislém bloku paměti. Přístup k prvku je bleskový, ale změna velikosti pole je náročná. * Spojový seznam (Linked List): Prvky jsou rozesety v paměti a každý prvek ukazuje na ten následující. Snadno se do něj vkládá, ale hledání v něm je pomalé. * Zásobník (Stack): Princip LIFO (Last In, First Out). Jako stoh talířů – poslední položený berete jako první. * Fronta (Queue): Princip FIFO (First In, First Out). Jako fronta v obchodě – kdo dřív přijde, je dřív obsloužen.
* Strom (Tree): Hierarchická struktura (např. souborový systém). Nejdůležitější je Binární vyhledávací strom, který umožňuje velmi rychlé hledání. * Graf (Graph): Množina uzlů propojených hranami. Používá se pro modelování sociálních sítí nebo map (navigace). * Hešovací tabulka (Hash Table): Umožňuje vyhledat hodnotu pomocí klíče v téměř konstantním čase.
[Image of Binary Search Tree and Graph data structure diagrams]
—
Algoritmus je konečná posloupnost přesně definovaných instrukcí pro vyřešení daného úkolu.
—
Abychom mohli porovnat, který algoritmus je lepší, používáme zápis Big O notation. Ten neříká, kolik sekund program poběží, ale jak poroste náročnost se zvyšujícím se množstvím dat ($n$).
| Složitost | Název | Příklad |
|---|---|---|
| $O(1)$ | Konstantní | Přístup k prvku v poli pomocí indexu. |
| $O(\log n)$ | Logaritmická | Binární vyhledávání (při každém kroku půlíme zbytek dat). |
| $O(n)$ | Lineární | Prohledání neseřazeného seznamu (musíme projít vše). |
| $O(n \log n)$ | Linearitmetická | Efektivní třídicí algoritmy (MergeSort). |
| $O(n^2)$ | Kvadratická | Neefektivní třídění (Bubble Sort - dva cykly v sobě). |
—
Související články:
Tagy: dev algorithms data_structures complexity sorting binary_tree