4IT218 — Webové technologie

O předmětu

Algoritmy a datové struktury jsou základem efektivního programování. Předmět tě naučí analyzovat časovou a prostorovou složitost algoritmů a vybírat správnou datovou strukturu pro každý problém.

Složitost algoritmů — Big O notace

Nejčastější složitosti (od nejlepší k nejhorší):

Složitost	Název	Příklad
O(1)	konstantní	přístup do pole, hashmap lookup
O(log n)	logaritmická	binární vyhledávání
O(n)	lineární	lineární vyhledávání
O(n log n)	linearitmická	quicksort, mergesort
O(n²)	kvadratická	bubble sort, insertion sort
O(2ⁿ)	exponenciální	Fibonacci rekurzí

Jak určit složitost:

// O(n) — jeden průchod polem
for (int i = 0; i < n; i++) { ... }

// O(n²) — vnořené smyčky
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) { ... }

// O(log n) — půlení rozsahu
int lo = 0, hi = n - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    // půlíme
}

Datové struktury

Pole (Array):

• Přístup: O(1), Vyhledávání: O(n), Vložení na konec: O(1) amortizovaně
• Pevná velikost, souvislá paměť

Spojový seznam (Linked List):

class Node {
    int data;
    Node next;
}

• Vložení na začátek: O(1), Přístup k prvku: O(n)
• Dynamická velikost, nevhodný pro náhodný přístup

Zásobník (Stack) — LIFO:

Deque stack = new ArrayDeque<>();
stack.push(1);      // vložení
int top = stack.pop(); // odebrání vrcholu
int peek = stack.peek(); // náhled bez odebrání

Použití: undo/redo, vyhodnocení výrazů, DFS

Fronta (Queue) — FIFO:

Queue queue = new LinkedList<>();
queue.offer(1);     // enqueue
int front = queue.poll(); // dequeue

Použití: BFS, zpracování požadavků

Prioritní fronta (Heap):

PriorityQueue pq = new PriorityQueue<>(); // min-heap
pq.offer(5); pq.offer(1); pq.offer(3);
pq.poll(); // vrátí 1 (minimum)

Vložení/odebrání: O(log n), Minimum: O(1)

HashMap:

• Průměrně O(1) pro get/put/remove
• Nejhorší případ O(n) při kolizích
• Load factor ~0.75

BST (Binary Search Tree):

• Průměrně O(log n), nejhůře O(n) (nevyvážený)
• Vlastnost: levý podstrom < uzel < pravý podstrom

Řadící algoritmy

Bubble Sort — O(n²):

for (int i = 0; i < n-1; i++)
    for (int j = 0; j < n-i-1; j++)
        if (arr[j] > arr[j+1]) swap(arr, j, j+1);

Merge Sort — O(n log n), stabilní:

void mergeSort(int[] arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    merge(arr, l, mid, r);  // sloučení dvou seřazených polí
}

Quick Sort — O(n log n) průměrně, O(n²) nejhůře:

void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partition(arr, lo, hi);
    quickSort(arr, lo, pivot-1);
    quickSort(arr, pivot+1, hi);
}

Binární vyhledávání — O(log n):

int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Rekurze

// Faktoriál
int faktorial(int n) {
    if (n <= 1) return 1;         // base case
    return n * faktorial(n - 1);  // recursive case
}

// Fibonacci — O(2ⁿ) bez memoizace!
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// Fibonacci s memoizací — O(n)
Map memo = new HashMap<>();
long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long result = fibMemo(n-1) + fibMemo(n-2);
    memo.put(n, result);
    return result;
}

Grafy

Reprezentace:

// Matice sousednosti — O(V²) paměť
int[][] adj = new int[V][V];
adj[u][v] = 1;

// Seznam sousednosti — O(V+E) paměť (lepší pro řídké grafy)
List> adj = new ArrayList<>();
adj.get(u).add(v);

BFS (prohledávání do šířky) — O(V+E):

void bfs(int start) {
    Queue q = new LinkedList<>();
    boolean[] visited = new boolean[V];
    q.offer(start); visited[start] = true;
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;
                q.offer(v);
            }
        }
    }
}

DFS (prohledávání do hloubky) — O(V+E):

void dfs(int u, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u))
        if (!visited[v]) dfs(v, visited);
}

Tipy pro zkoušku

• Big O: ignoruj konstanty a nižší řády — O(3n² + 2n + 5) = O(n²)
• Rekurze = zásobník volání, hloubka rekurze = paměť
• HashMap vs TreeMap: HashMap O(1) průměrně, TreeMap O(log n) ale seřazený
• Merge sort je stabilní, quick sort není (záleží na implementaci)
• Dijkstrův algoritmus pro nejkratší cestu — O((V+E) log V) s priority queue

Doporučené zdroje

• Visualgo — animace algoritmů
• Big-O Cheat Sheet
• Kniha: Introduction to Algorithms (CLRS) — bible algoritmů
• LeetCode — procvičování algoritmických úloh