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

1. 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, karddisk
• 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

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.

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.

Výsledky sú závislé na konkrétnej imlementácii, na konkrétnych dátach a na konkrétnom hardvéri

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

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ýšlač

2. Čo je asymptotická zložitosť?

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

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.

3. 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

4. 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

5. 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

6. 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

7. 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

8. 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)

9. 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.

10. Porovnanie rastu

Od najlepšieho po najhorší:

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

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)

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 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)

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

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ť.

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.

11. 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

✅ Efektívne – 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

🎓 13. 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

14. 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

15. 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

16. 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

17. Merge Sort – O(n log n)

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

Myšlienka:

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

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

Zložitosť:

• vždy: O(n log n)

👉 Stabilný a spoľahlivý algoritmus

18. 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

19. Built-in Python sort (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

20. Porovnanie algoritmov

21. 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

22. Kedy použiť čo?

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

23. Mini cvičenie

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

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

24. Abstraktné stroje pre analýzu zložitosti

Analýza asymptotickej zložitosti pomocou abstraktných strojov:

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

📚 Referencie: EMU Studio

🔚 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)