Ako sa meria a opisuje zložitosť algoritmov?

Zložitosť algoritmov sa zvyčajne meria z hľadiska časovej a priestorovej zložitosti, ktoré popisujú, ako sa zvyšuje počet operácií (čas) a využívaná pamäť (priestor) v závislosti od veľkosti vstupných dát.

Najčastejšie používanou notáciou je "Big O", ktorá ukazuje hornú hranicu rastu spotreby zdrojov algoritmu pri zvyšovaní vstupných dát. Napríklad:

• O(1) — konštantná zložitosť, čas nezávisí od veľkosti vstupu.
• O(n) — lineárna, čas rastie úmerne veľkosti vstupu.
• O(n²) — štvorcová, čas rastie úmerne štvorcu veľkosti vstupu.

Príklad v jazyku Java na výpočet súčtu prvkov poľa s lineárnou zložitosťou O(n):

public int sum(int[] arr) {
    int total = 0;
    for (int num : arr) {
        total += num;
    }
    return total;
}

Tu závisí doba behu od dĺžky poľa, preto je zložitosť — O(n). Hodnotenie algoritmov pomáha pri výbere najefektívnejších riešení, najmä pri práci s veľkými dátami.