vyhľadávanie a triedenie
O(1), O(log n), O(n), O(n²)Keď píšeme programy, nestačí, aby „fungovali“. Musia byť aj efektívne.
Potrebujeme:
máme dva rôzne algoritmy vyhľadávania v poli veľkosti N. Jeden (A) je implementovaný v C++, druhý (B) v Pythone.
Veľkosť zoznamu n |
Počítač A (ns) | Počítač B (ns) |
|---|---|---|
| 16 | 8 | 100 000 |
| 63 | 32 | 150 000 |
| 250 | 125 | 200 000 |
| 1 000 | 500 | 250 000 |
Na prvý pohľad vyzerá algoritmus A výrazne lepšie
Veľkosť zoznamu n |
Algoritmus A (ns) | Algoritmus B (ns) |
|---|---|---|
| 1 000 000 | 500 000 | 500 000 |
| 4 000 000 | 2 000 000 | 550 000 |
| 16 000 000 | 8 000 000 | 600 000 |
| 63 072 × 10¹² | 1 rok | 1,375 ms |
Výsledky znázorníme ako krivku závislosti veľkosti dát a potrebného času alebo potrebnej pamäte
T (s)
^
| *
| *
| *
| *
| *
| *
+---------------------------> NExponenciálna krivka na začiatku vyzerá ako lineárna
T (s)
^
| x*
| x *
| x *
| x *
| x *
| ..... x .... * ............
| x *
| x *
| x*
+---------------------------> NPo čase exponenciálna krivka pretne lineárnu, nezávisle od konštánt
Ktorá krivka je lepšia?
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.
Pre získanie všeobecného porovnania je potrebná teoretická analýza:
Potom nemusíme nič programovať a spúšťať, stačí porozmýšľať.
umožnia analyzovať algoritmy nezávisle od konkrétnej implementácie a hardvéru.
Definujú množinu operácií, ktoré trvajú jednu jednotku času.
📚 Referencie: EMU Studio
Štart funkcie potrebuje S operácií, jeden cyklus C operácií. Pole má veľkosť N.
def find(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Popisuje, podľa ktorej krivky sa mení počet teoretických operácií v závislosti od veľkosti vstupu n.
Základné triedy zložitosti algoritmov:
Používame najmä:
👉 Ignorujeme konštanty a menej významné členy.
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
Č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
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
V každej iterácii 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 -1Od najlepšieho po najhorší:
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)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²)Vyhľadávanie znamená nájsť prvok v kolekcii.
Typické otázky:
Zložitosť závisí od toho, či sú dáta usporiadané.
Prechádzame prvky jeden po druhom.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1Zložitosť:
Lineárne vyhľadávanie je vhodné, keď:
Nevýhoda:
pri veľkom n môže byť pomaléBinárne vyhľadávanie funguje iba na zoradených dátach.
Myšlienka:
Každým krokom zmenšíme problém približne na polovicu.
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 -1Zložitosť: O(log n)
Hľadáme 23:
[2, 5, 8, 12, 16, 23, 38, 56]
↑
1223 je väčšie ako 12, ľavú polovicu zahodíme.
[16, 23, 38, 56]
↑
23Hodnota bola nájdená.
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ť.
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.
Triedenie je základ pre:
Jednoduchý, ale neefektívny algoritmus.
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]👉 Veľmi pomalý pre veľké dáta
V každom kroku nájdeme najmenší prvok a dáme ho na správne miesto.
👉 Jednoduchý, ale neefektívny
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
# Hľadáme index s najmenším prvkom
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# Vymenime aktualny a najmensi prvok
arr[i], arr[min_idx] = arr[min_idx], arr[i]
# na indexe i je potom vždy najmenší prvok zo zvyšku poľaBudujeme zoradenú časť poľa postupne.
👉 V praxi veľmi dobrý pre malé alebo skoro zoradené polia
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] = keyEfektívny algoritmus založený na divide & conquer.
Zložitosť: O(n log n)
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👉 Veľmi rýchly v praxi, ale závisí od pivotu
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)arr.sort()
# alebo
sorted_arr = sorted(arr)👉 Kombinácia:
✔ Optimalizovaný pre reálne dáta ✔ Používa sa v praxi
📚 Timsort
| Algoritmus | Najhorší prípad | Priemerný | Najlepší |
|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(n) |
| Selection Sort | O(n²) | O(n²) | O(n²) |
| Insertion Sort | O(n²) | O(n²) | O(n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Quick Sort | O(n²) | O(n log n) | O(n log n) |
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
Skús určiť zložitosť:
def mystery(n):
i = 1
while i < n:
print(i)
i *= 2Očakávaná zložitosť: O(log n).
sorted(arr)