Teorie algoritmů – lineární

a kvadratická časová složitost

Časová složitost algoritmu patří mezi základní parametry, kterými se hodnotí efektivita algoritmických řešení. Je vyjádřena pomocí notace Big-O, jež popisuje, jak se doba běhu algoritmu mění v závislosti na velikosti vstupních dat (n). Tento článek se zaměřuje na dvě nejčastěji analyzované třídy algoritmů – lineární časovou složitost O(n) a kvadratickou časovou složitost O(n²). Tyto dvě složitosti se objevují napříč mnoha oblastmi informatiky, od vyhledávání a procházení datových struktur až po řadicí algoritmy.

Lineární časová složitost — O(n)

Algoritmus s časovou složitostí O(n) má dobu běhu přímo úměrnou počtu vstupních prvků. Pokud se vstup zdvojnásobí, přibližně se zdvojnásobí i doba provedení.

Typické vlastnosti:

obsahuje jednu smyčku procházející prvky,

operace uvnitř smyčky má konstantní čas,

algoritmus nezanořuje další cykly.

Typické příklady

lineární vyhledávání (Linear Search),

součet prvků seznamu,

kontrola existence prvku,

průchod grafu BFS/DFS (zjednodušeně).

Příklad programu v Pythonu – Lineární hledání


    def linear_search(arr, target):
        for index, value in enumerate(arr):
            if value == target:
                return index  # vrací index nalezeného prvku
        return -1  # prvek nebyl nalezen


    # Ukázka použití
    data = [4, 8, 1, 7, 9, 3]
    print(linear_search(data, 7))

Analýza

Smyčka proběhne maximálně n prvků → O(n).

Kvadratická časová složitost — O(n²)

Algoritmy s časovou složitostí O(n²) vykazují kvadratický růst počtu operací ve vztahu k velikosti vstupu. Pokud n zdvojnásobíme, doba běhu se přibližně čtyřnásobí.

Typické vlastnosti:

vyskytuje se dvojité zanoření cyklů,

algoritmus porovnává každý prvek s každým,

často jde o jednoduché implementace řadicích algoritmů.

Typické příklady

Bubble Sort,

Insertion Sort,

Selection Sort,

generování všech dvojic prvků (kombinace),

matice a operace nad ní (bez optimalizací).

Příklad programu v Pythonu – Bubble Sort


    def bubble_sort(arr):
        n = len(arr)
        for i in range(n):
            for j in range(0, n - i - 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr


    # Ukázka použití
    data = [5, 2, 9, 1, 5, 6]
    print(bubble_sort(data))

Analýza

Dvojice zanořených smyček → přibližně n × n iterací → O(n²).

Srovnání lineární a kvadratické složitosti

Kvadratická složitost se stává problematickou u větších datových množin (např. tisíce prvků). Pro výuky algoritmů je důležité, aby studenti uměli analyzovat chování algoritmů ještě před implementací.

Praktické doporučení pro studenty

vždy analyzujte, zda algoritmus obsahuje jednu nebo dvě smyčky, dejte pozor na algoritmy porovnávající „každý s každým“, preferujte lineární nebo logaritmické algoritmy, pokud je to možné, kvadratické algoritmy používejte hlavně ve výuce nebo při malých datech.

Lineární a kvadratická časová složitost jsou základní stavební kameny pro pochopení efektivity algoritmů. Znalost těchto konceptů umožňuje studentům informatiky správně volit datové struktury, psát efektivní programy a optimalizovat výkon software. Přestože jednoduché implementace často vedou k O(n²), systematická analýza pomáhá nalézt efektivnější řešení.