Zložitosť algoritmov

📅   03. 08. 2021
👤   Jan Barášek

Každý algoritmus má svoju vlastnú zložitosť, ktorú možno vyjadriť matematickým zápisom. Tento prehľad ukazuje typickú zložitosť algoritmov v závislosti od veľkosti vstupných údajov (t. j. počtu prvkov, s ktorými pracujú) a od toho, ktoré typy algoritmov sú vhodné pre ktorý typ úlohy.

Vo všeobecnosti existuje najlepší špecializovaný algoritmus pre každý typ problému. Žiadny algoritmus nie je univerzálne najlepší a vždy musíte poznať kontext.

Zápis Big O

Zápis Big O sa používa na klasifikáciu algoritmov podľa toho, ako sa ich požiadavky na čas behu alebo pamäť zvyšujú s rastúcou veľkosťou vstupu.

Nasledujúca tabuľka zobrazuje najčastejšie príkazy rastu algoritmov zadaných v notácii Big O.

Nižšie je uvedený zoznam niektorých najčastejšie používaných zápisov Big O a porovnanie ich výkonnosti vzhľadom na rôzne veľkosti vstupných údajov.

Big O Notation Zložitosť pre 10 prvkov Zložitosť pre 100 prvkov Zložitosť pre 1000 prvkov
O(1) 1 1 1
O(log N) 3 6 9
O(N) 10 100 1000
O(N log N) 30 600 9000
O(N^2) 100 10000 1000000
O(2^N) 1024 1,26e+29 1,07e+301
O(N!) 3628800 9,3e+157 4,02e+2567

Zložitosť operácií s dátovými štruktúrami

Dátová štruktúra Prístup Vyhľadávanie Vloženie Odstránenie Komentár
Array 1 n n n n
Stack n n n 1 1
Queue n n n 1
Soznam odkazov n n n 1 n
Hash tabuľka - n n n n
Binárny vyhľadávací strom n n n n V prípade vyváženého stromu bude zložitosť O(log(n)).
B-strom log(n) log(n) log(n) log(n) log(n)
Červeno-čierny strom log(n) log(n) log(n) log(n)
AVL Tree log(n) log(n) log(n) log(n) log(n)
Filter rozkvetu - 1 1 - Pri vyhľadávaní falošne pozitívnych výsledkov

Zložitosť triediacich algoritmov

Názov algoritmu Najlepší Priemerný Najhorší Pamäť Stabilný? Komentár
Bubble sort n n2 n2 1 Áno
Triedenie vkladania n n2 n2 1
Triedenie výberu n2 n2 n2 1
Heap sort n log(n) n log(n) n log(n) 1 Nie
Spojiť triedenie n log(n) n log(n) n log(n) n Áno
Quick sort n log(n) n log(n) n2 log(n) Nie
Shell sort n log(n) závisí od postupnosti n (log(n))2 1 Nie
Triedenie podľa počtu n + r n + r n + r n + r Áno r - najväčšie číslo v poli
Radix sort n * k n * k n * k n + k Áno k - dĺžka najdlhšieho kľúča

Jan Barášek     Viac o autorovi

Autor pracuje ako senior vývojár a softvérový architekt v Prahe. Navrhuje a spravuje veľké webové aplikácie, ktoré poznáte a používate. Od roku 2009 získal bohaté skúsenosti, ktoré odovzdáva prostredníctvom tejto webovej stránky.

Rád vám pomôžem:

Kontakt