Asymptotická zložitosť (Big-O)

vyhľadávanie A triedenie

Osnova

• Prečo riešime zložitosť algoritmov
• Základné triedy zložitosti: O(1), O(log n), O(n), O(n²)
• Kombinovaná zložitosť, prípady výpočtu a rast funkcií
• Vyhľadávanie: lineárne, binárne a pomocou množiny
• Praktická analýza rôznych riešení
• Triediace algoritmy a ich porovnanie
• Mini cvičenie a abstraktné stroje
• Záver

Prečo nás zaujíma zložitosť?

Keď píšeme programy, nestačí, aby „fungovali“. Musia byť aj efektívne.

Koľko prostriedkov a zdrojov je potrebné na vyriešenie úlohy:

• pamäť: RAM, pevný disk
• procesory, CPU, GPU
• čas spracovania
• elektrická energia

Benchmarking

empirické meranie času potrebného na vykonanie konkrétnej úlohy na konkrétnej hardvérovej konfigurácii.

"lepší" hardvér - potrebuje menej času

Benchmark hovorí o výkone hardvéru, ale nehovorí o efektivite implementácie úlohy

📚 Benchmark (výpočtová technika)

Ako hodnotíme "Výkonnosť" algoritmu?

• Algoritmus môže bežať na rôznom hardvéri

• Algoritmus môže spracovávať rôzne množstvo dát.

• Emprické meranie je závislé od konkrétnej implementácie, konkrétnych dát a konkrétneho hardvéru.

• Teoretická analýza umožní porovnávať algoritmy podľa toho, ako rastie ich náročnosť pri zväčšovaní vstupu.

Empirická analýza (benchmark):

Výkonnosť algoritmu môžeme benchmarkovať:

• na tom istom hardvéri spustíme úlohu s rôznym množstvom dát
• koľko času a pamäte potrebujeme?

Potrebujeme:

• implementáciu
• vzorové dáta rôznej veľkosti
• fyzicky spustiť úlohy.

Chceme porovnať algoritmy, nie konkrétne implementácie.

Ktorý algoritmus je lepší nezávisle od množstva dát a dostupných prostriedkov?

Merať vieme len s konkrétnymi dátami a s konkrétnou implementáciou.

Príklad: máme dva rôzne algoritmy, ktoré riešia rovnakú úlohu. Jeden je implementovaný v Pythone, druhý v C++. Ktorý je lepší?

Benchmark: malé vstupy

Na prvý pohľad vyzerá algoritmus na počítači A výrazne lepšie:

Počítač A je však rýchlejší hardvér, nie nevyhnutne lepší algoritmus.

Benchmark: veľké vstupy

Pri dostatočne veľkom vstupe sa situácia obráti:

Počítač A používa lineárne vyhľadávanie: dvojnásobný vstup znamená približne dvojnásobný čas. Počítač B používa binárne vyhľadávanie: čas rastie logaritmicky. Preto môže pomalší počítač s lepším algoritmom časom zvíťaziť.

📚 Algoritmická efektívnosť na Wikipédii

Výsledky znázorníme ako krivku závislosti veľkosti dát a potrebného času alebo potrebnej pamäte

T (s)
^
|                  *
|                *
|             *
|          *
|      *
|  *
+---------------------------> N

Ktorá krivka je lepšia?

• lineárna?
• kvadratická?
• log lineárna?
• kubická?

Príklady na krivky:

T (s)
^
|           x     *
|         x      *
| ..... x .... * ............
|     x     *
|   x   *
| x*
+---------------------------> N

Benchmark verzus teoretická analýza

Benchmark závisí od konkrétnej implementácie, dát a hardvéru. Teoretická analýza umožní porovnávať algoritmy podľa toho, ako rastie ich náročnosť pri zväčšovaní vstupu.

📚 Analýza algoritmov na Wikipédii

Pre získanie všeobecného porovnania je potrebná teoretická analýza:

• definujeme teoretickú jednotku výpočtu
• definujeme teoretickú veľkosť dát.

Potom nemusíme nič programovať a spúšťať, stačí porozmýšľať.

Abstraktné stroje pre analýzu zložitosti

Pre zjednodušenie analýzy zložitosti používame abstraktné stroje. Tie nám umožnia analyzovať algoritmy nezávisle od konkrétnej implementácie a hardvéru.

• RAM model (Random Access Machine)
• RASP model (Register Abstract Storage Machine)

📚 Referencie: EMU Studio

📚 Model RAM na Wikipédii

Čo je asymptotická zložitosť?

Popisuje, ako sa mení počet teoretických operácií v závislosti od veľkosti vstupu n.

• v najlepšom prípade: dáta sú priaznivé, algoritmus nájde riešenie hneď
• v priemernom prípade: dáta sú náhodné, algoritmus pracuje priemerna
• v najhoršom prípade: dáta sú nepriaznivé, algoritmus musí prejsť všetky možnosti

Pri analýze zložitosti sa zameriavame na najhorší prípad.

Najlepší, priemerný a najhorší prípad

Niektoré algoritmy sa správajú rôzne:

def find(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

• najlepší prípad: O(1) (nájde hneď)
• najhorší: O(n)
• priemerný: O(n)

📚 Analýza algoritmov

Pri asymptotickej zložitosti sa zameriavame na rast funkcie. Konštanty zanedbávame, pretože pri veľkých vstupoch sú zanedbateľné.

📚 Big O notácia na Wikipédii

Príklady zápisu Big-O

Zanedbávame konštanty a menej významné členy:

3n + 1 -> O(n)

4n² + 3n + 1 -> O(n²)

2x^2 log(x) + 3x -> O(x² log(x))

x^2 + 4x log(x) + 7 -> O(x²)

Prečo ignorujeme konštanty?

def f1(arr):
    for x in arr:
        print(x)

def f2(arr):
    for x in arr:
        print(x)
        print(x)
        print(x)

• f1: O(n)
• f2: O(3n) → O(n)

👉 Konštanta (3) nie je dôležitá pri veľkých n.

📚 Big O notácia

Kombinovaná zložitosť

Niektoré algoritmy majú viac častí:

def example(arr):
    # O(n)
    for x in arr:
        print(x)

    # O(n²)
    for i in arr:
        for j in arr:
            print(i, j)

👉 Výsledná zložitosť:

O(n + n²) = O(n²)

✔ Berieme najdominantnejší člen

📚 Asymptotická analýza

Základné triedy zložitosti algoritmov:

Používame najmä:

• O(1) – konštantná - potrebný čas je stále rovnaký
• O(n) – lineárna - potrebný čas je priamo úmerný veľkosti vstupu
• O(n²) – kvadratická - potrebný čas je druhou mocninou veľkosti vstupu
• O(log n) – logaritmická - potrebný čas rastie pomalšie ako priama úmera.

👉 Ignorujeme konštanty a menej významné členy.

O(1) – konštantná zložitosť

Operácia trvá rovnako dlho bez ohľadu na veľkosť vstupu.

def get_first(arr):
    return arr[0]

✔ Vždy 1 operácia ✔ Nezáleží na veľkosti poľa

📚 Algoritmická efektívnosť

O(n) – lineárna zložitosť

Čas rastie priamo úmerne s n.

def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

✔ Pre každý prvok robíme jednu operáciu ✔ Pri dvojnásobnom vstupe → dvojnásobný čas

📚 Lineárne vyhľadávanie

O(n²) – kvadratická zložitosť

Typicky vnorené cykly.

def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

✔ Počet operácií ≈ n × n ✔ Veľmi rýchlo rastie

📚 Rastová miera

O(log n) – logaritmická zložitosť

Zmenšujeme problém na polovicu (napr. binárne vyhľadávanie).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

✔ Každým krokom zmenšíme problém na polovicu ✔ Veľmi efektívne aj pre veľké dáta

📚 Binárne vyhľadávanie

Porovnanie rastu

Od najlepšieho po najhorší:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

📚 Porovnanie rastových mier

Vyhľadávanie

Vyhľadávanie znamená nájsť prvok v kolekcii.

Typické otázky:

• Nachádza sa prvok v zozname?
• Na akom indexe sa nachádza?
• Existuje prvok s danou vlastnosťou?

Zložitosť závisí od toho, či sú dáta usporiadané.

Lineárne vyhľadávanie

Prechádzame prvky jeden po druhom.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

Zložitosť:

• najlepší prípad: O(1)
• najhorší prípad: O(n)
• priemerný prípad: O(n)

📚 Lineárne vyhľadávanie

Kedy použiť lineárne vyhľadávanie?

Lineárne vyhľadávanie je vhodné, keď:

• dáta nie sú zoradené,
• kolekcia je malá,
• vyhľadávame iba raz,
• nechceme platiť cenu za triedenie.

Nevýhoda:

pri veľkom n môže byť pomalé

Binárne vyhľadávanie

Binárne vyhľadávanie funguje iba na zoradených dátach.

Myšlienka:

1. pozri sa do stredu,
2. rozhodni, v ktorej polovici môže byť hľadaná hodnota,
3. druhú polovicu zahodíš,
4. opakuj.

Každým krokom zmenšíme problém približne na polovicu.

📚 Binárne vyhľadávanie

Binárne vyhľadávanie v Pythone

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Zložitosť: O(log n)

📚 Binárne vyhľadávanie

Priebeh binárneho vyhľadávania

Hľadáme 23:

[2, 5, 8, 12, 16, 23, 38, 56]
             ↑
            12

23 je väčšie ako 12, ľavú polovicu zahodíme.

[16, 23, 38, 56]
      ↑
     23

Hodnota bola nájdená.

Lineárne vs binárne vyhľadávanie

📚 Lineárne vyhľadávanie, binárne vyhľadávanie

Cena za zoradenie

Ak dáta ešte nie sú zoradené, binárne vyhľadávanie vyžaduje triedenie.

arr = sorted(arr)          # O(n log n)
index = binary_search(arr, target)  # O(log n)

Pre jedno vyhľadanie sa to nemusí oplatiť.

Pre veľa vyhľadávaní nad rovnakými dátami sa triedenie môže vyplatiť.

📚 Triediaci algoritmus

Vyhľadávanie pomocou množiny

Ak nás zaujíma iba existencia prvku, často je vhodná množina.

items = {10, 20, 30, 40}

print(30 in items)

Priemerná zložitosť:

O(1)

Množina používa hash tabuľku.

📚 Hašovacia tabuľka

Praktický príklad – rôzne riešenia

Príklad analýzy asymptotickej zložitosti

Problém: Nájsť duplicity v poli

❌ Neefektívne – O(n²)

def has_duplicates(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

Zložitosť je O(n²), pretože porovnávame dvojice prvkov.

Efektívne riešenie – O(n)

def has_duplicates(arr):
    seen = set()

    for x in arr:
        if x in seen:
            return True
        seen.add(x)

    return False

✔ Použitie množiny (set) dramaticky zlepší výkon

Zložitosť je priemerné O(n) a pomocná pamäť má zložitosť O(n).

📚 Detekcia duplicít

🎓 Triedacie algoritmy a ich zložitosť

Prečo riešiť triedenie?

Triedenie je základ pre:

• vyhľadávanie (binary search funguje len na zoradených dátach)
• databázy
• optimalizáciu algoritmov

📚 Triediaci algoritmus

Bubble Sort – O(n²)

Jednoduchý, ale neefektívny algoritmus.

Myšlienka:

Opakovane prechádzame pole a vymieňame susedné prvky, ak sú v zlom poradí.

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]

Zložitosť:

• najhorší: O(n²)
• priemerný: O(n²)
• najlepší: O(n) (ak už je zoradené + optimalizácia)

👉 Veľmi pomalý pre veľké dáta

📚 Bubble sort

Selection Sort – O(n²)

Myšlienka:

V každom kroku nájdeme najmenší prvok a dáme ho na správne miesto.

def selection_sort(arr):
    n = len(arr)

    for i in range(n):
        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Zložitosť:

• vždy: O(n²)

👉 Jednoduchý, ale neefektívny

📚 Selection sort

Insertion Sort – O(n²), ale...

Myšlienka:

Budujeme zoradenú časť poľa postupne.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

Zložitosť:

• najhorší: O(n²)
• najlepší: O(n) (takmer zoradené dáta)

👉 V praxi veľmi dobrý pre malé alebo skoro zoradené polia

📚 Insertion sort

Merge Sort – myšlienka

Efektívny algoritmus založený na divide & conquer.

Myšlienka:

• rozdel pole na polovice
• zorad každú polovicu
• spoj ich

Zložitosť: O(n log n)

📚 Merge sort

Merge Sort – implementácia

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

👉 Stabilný a spoľahlivý algoritmus

📚 Merge sort

Quick Sort – priemerne O(n log n)

Myšlienka:

• vyber pivot
• rozdeľ na menšie a väčšie
• rekurzívne tried

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

Zložitosť:

• priemerná: O(n log n)
• najhoršia: O(n²)

👉 Veľmi rýchly v praxi, ale závisí od pivotu

📚 Quicksort

Zabudované triedenie v Pythone (Timsort)

arr.sort()
# alebo
sorted_arr = sorted(arr)

Zložitosť:

• najhorší: O(n log n)
• najlepší: O(n)

👉 Kombinácia:

• Merge Sort
• Insertion Sort

✔ Optimalizovaný pre reálne dáta ✔ Používa sa v praxi

📚 Timsort

Porovnanie triediacich algoritmov

📚 Porovnanie triediacich algoritmov

Praktická ukážka rozdielu

import random
import time

arr = [random.randint(0, 10000) for _ in range(1000)]

start = time.time()
sorted(arr)  # Timsort
print("Built-in:", time.time() - start)

start = time.time()
bubble_sort(arr.copy())
print("Bubble:", time.time() - start)

👉 Rozdiel môže byť stokrát až tisíckrát

📚 Timsort

Kedy použiť ktorý algoritmus?

• malé dáta → Insertion Sort
• veľké dáta → Merge / Quick / built-in
• skoro zoradené → Insertion alebo Timsort
• garantovaný výkon → Merge Sort

📚 Triediaci algoritmus

Mini cvičenie

Skús určiť zložitosť:

def mystery(n):
    i = 1
    while i < n:
        print(i)
        i *= 2

Očakávaná zložitosť: O(log n).

📚 Logaritmus

🔚 Záver

• Asymptotická zložitosť hovorí, ako rastie čas algoritmu
• Najčastejšie používame Big-O notáciu
• Dôležité triedy: O(1), O(log n), O(n), O(n²)
• Ignorujeme konštanty, sledujeme najhorší prípad
• Triedenie krásne ukazuje rozdiel medzi O(n²) (pomalé) a O(n log n) (efektívne)
• V praxi takmer vždy použi sorted(arr)

📚 Algoritmická efektívnosť