Project Technical Lead
Big O notácia: analýza zložitosti algoritmov
Vývojári sa už od začiatku nástupu informačných technológií snažia písať kód, ktorý nielen funguje, ale aj efektívne využíva hardvér. Kedysi, keď procesory boli drahé a pomalé a pamäte málo, sa výrazne optimalizovalo a záležalo doslova na každej strojovej inštrukcii. Podobne to bolo pri práci s veľkými množinami údajov a algoritmy museli byť veľmi sofistikované, pretože výpočtový čas bol do veľkej miery limitovaný.
Preto vznikla potreba porovnávať efektivitu algoritmov a práve toto je miesto, kde notácia Big O zohráva významnú úlohu. V tomto článku sa pozrieme bližšie na analýzu algoritmickej zložitosti pomocou notácie Big O.
Big O notácia – čo to vlastne je?
BIG O notácia je matematický zápis v počítačovej vede, ktorá sa používa na opis asymptotickej zložitosti algoritmov, to znamená opisuje najhorší možný scenár (hornú hranicu) algoritmu na základe veľkosti vstupných dát. Inými slovami, táto notácia nám pomáha pochopiť, ako sa mení efektívnosť algoritmu v závislosti od množstva údajov, ktoré sa využívajú.
Krátka história BIG O zápisu
Jej teoretické základy boli položené začiatkom dvadsiateho storočia, keď ľudia o počítačových algoritmoch ani nesnívali, avšak v počítačovej vede sa Big O notácia stala populárnou a široko používanou až v 60. rokoch 20. storočia, hlavne vďaka priekopníkom ako Donald Knuth. Knuth podrobne rozpracoval a popularizoval používanie tejto notácie vo svojom známom diele The Art of Computer Programming, prvýkrát publikovanom v roku 1968. Knuthovo dielo významne prispelo k štandardizácii a rozšíreniu používania Big O notácie v analýze algoritmov a počítačových programov.
Použitie a vlastnosti BIG O notácie
Zápis BIG O sa používa na teoretické porovnanie efektivity rôznych algoritmov. Napr. ak sa rozhodujeme, ktorý triediaci algoritmus je vhodnejšie v danej situácii použiť, pozrieme si zápis pre rôzne algoritmy.
Rovnako nám pomáha predpovedať, ako sa bude algoritmus správať s množstvom narastajúcich vstupných údajov. Táto znalosť je nevyhnutným predpokladom pre optimalizovanie algoritmu a efektívnejšie využívanie zdrojov.
Pri riešení zložitých problémov môže znalosť zložitosti veľkého O rôznych algoritmov viesť k výberu vhodných dátových štruktúr a algoritmov. To nám pomáha navrhnúť efektívne riešenia problémov v reálnom svete.
Táto notácia sa používa pri analýze časovej a priestorovej zložitosti algoritmov. Časovú zložitosť sme už spomínali, priestorová zložitosť je vyjadrená pomocou notácie Big O na opis hornej hranice využitia pamäte algoritmom.
Pochopenie zápisu BIG O
V zápise Big O predstavuje O poradie funkcie a f(n) predstavuje funkciu popisujúcu časovú zložitosť algoritmu z hľadiska vstupnej veľkosti n. Zápis O(f(n)) znamená, že časová zložitosť algoritmu nerastie rýchlejšie ako špecifická funkcia so vstupom n. Matematická funkcia f(n) teda popisuje, ako sa zvyšuje doba behu algoritmu s rastúcou veľkosťou vstupu. Napr. zápis O(n) hovorí, že čas vykonávania algoritmu rastie lineárne s veľkosťou vstupu.
BIG O notácia – príklady
Teraz si ukážeme najpoužívanejšie typy zložitosti, ako sa zapisujú pomocou BIG o notácie a príklad algoritmu s danou zložitosťou v prehľadnej tabuľke.
| BIG O zápis | Zložitosť | Príklad algoritmu |
| O(1) | konštantná | Prístup k prvku v poli pomocou indexu |
| O(log n) | logaritmická | Binárne vyhľadávanie v zotriedenom poli |
| O(n) | lineárna | Lineárne vyhľadávanie cez nezoradené pole |
| O(n log n) | linearitmická | Efektívne triediace algoritmy ako napr. mergesort |
| O(n²) | kvadratická | 2 vnorené slučky iterujúce cez vstup |
| O(2n) | exponenciálna | Brute force algoritmy testujúce všetky kombinácie |
| O(n!) | faktorová | Algoritmus generujúce všetky permutácie množiny |
Pravidlá používania notácie Big O
Pri používaní Big O notácie existuje niekoľko základných pravidiel, ktoré pomáhajú presne a konzistentne vyjadriť asymptotickú zložitosť algoritmov. Big O notácia sa dá používať rovnako pre časovú aj priestorovú zložitosť.
Ignorovanie nižších rádov
Pri určovaní Big O notácie sa berie do úvahy iba najvyšší rád. Nižšie rády a konštanty sú zanedbateľné, pretože ich vplyv sa stáva zanedbateľným pri veľkých vstupoch.
Príklad: Ak má algoritmus časovú zložitosť f(n) = 3n² + 5n + 82, zložitosť je O(n²) , pretože n² je najvyšší rád.
Ignorovanie konštánt
Konštantné faktory sú zanedbateľné, pretože nemajú významný vplyv na rast funkcie pri veľkých vstupoch.
Príklad: Ak má algoritmus časovú zložitosť f(n) = 2n, zložitosť je O(n) .
Súčet
Ak je algoritmus zložený z niekoľkých krokov, ktoré sa vykonávajú sekvenčne, celková zložitosť je určená najvyšším rádom medzi jednotlivými krokmi.
Príklad: Ak má algoritmus dve časti so zložitosťou O(n) a O(n²), celková zložitosť je O(n²).
Súčin
Ak algoritmus obsahuje vnorené cykly, celková zložitosť je súčinom zložitostí jednotlivých cyklov.
Príklad: Ak má vonkajší cyklus zložitosť O(n)) a vnútorný cyklus tiež zložitosť O(n), celková zložitosť je O(n * n) = O(n²).
Logaritmy
Logaritmické funkcie rastú pomalšie ako polynomiálne funkcie, takže sú často v praxi zanedbateľné oproti polynomiálnym.
Náš tip – praktické využitie pri programovaní
Ak sme naimplementovali nejaký algoritmus a chceme zistiť jeho zložitosť bez toho, aby sme si začali analyzovať časové zložitosti jednotlivých blokov kódu, môžeme daný algoritmus postupne spúšťať pre vstupné dáta 1 až N a odmerať si čas behu rutiny. Z týchto nameraných hodnôt si potom vieme v Exceli zostrojiť graf závislosti vstupných dát (osa x) od času priebehu algoritmu (osa y). Podľa tvaru krivky potom vieme približne identifikovať zložitosť algoritmu a v závislosti od typu algoritmu potom zistíme, či existuje priestor na jeho optimalizáciu.
