📊 Анализ на алгоритми. Бързо търсене и бързо сортиране

⚖️ Дълбок анализ на алгоритми

В състезателното програмиране не е достатъчно просто да напишем работещ код. Той трябва да работи в рамките на времевото ограничение (обикновено 1 секунда). Съвременните съдии изпълняват около \(10^8\) операции в секунда.

🕒 Сложност по време и Ограничения (Time Complexity)

Познаването на ограниченията на входните данни (\(N\)) често ни подсказва необходимата сложност на решението:

Ограничение за \(N\)	Допустима сложност	Типични алгоритми
\(N \le 10\)	\(O(N!)\)	Пълно изчерпване (Backtracking), Пермутации
\(N \le 20\)	\(O(2^N)\)	ДП с битови маски, Recursion
\(N \le 500\)	\(O(N^3)\)	Флойд-Уоршал, Умножение на матрици, ДП
\(N \le 2000\)	\(O(N^2)\)	Bubble/Insertion Sort, ДП, BFS/DFS от всеки връх
\(N \le 100,000\)	\(O(N \log N)\)	Sorting, Heap, Segment Tree, Binary Search
\(N \le 1,000,000\)	\(O(N)\) или \(O(N \log N)\)	KMP, Hash, Two Pointers, Union-Find
\(N \ge 10^{18}\)	\(O(\log N)\) или \(O(1)\)	Матрично повдигане, Математически формули

📜 Master Theorem (За рекурсивни алгоритми)

За рекуррентна връзка от вида \(T(n) = a T(n/b) + f(n)\): 1. Ако \(f(n) = O(n^c)\) и \(c < \log_b a\), то \(T(n) = \Theta(n^{\log_b a})\). 2. Ако \(f(n) = \Theta(n^c \log^k n)\) и \(c = \log_b a\), то \(T(n) = \Theta(n^c \log^{k+1} n)\). 3. Ако \(f(n) = \Omega(n^c)\) и \(c > \log_b a\), то \(T(n) = \Theta(f(n))\).

🔍 Бързо търсене (Двоично търсене) - Разширено

Двоичното търсене не е само за намиране на число в масив. То е мощен метод за намиране на отговор на задача, ако отговорът е монотонен.

1. Стандартно двоично търсене (`std::lower_bound`)

Намира първия елемент, който е \(\ge\) на търсения.

int lowerBound(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size(); // Внимавайте с границите [0, N)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left; // Връща индекс или N, ако няма такъв
}

2. Двоично търсене по отговор (Binary Search on Answer)

Използва се, когато търсим минимална стойност \(X\), за която условие \(P(X)\) е изпълнено (и за всяко \(Y > X\), \(P(Y)\) също е изпълнено).

Пример: "Какво е минималното време, за което \(K\) машини могат да произведат \(M\) продукта?" - Функцията check(time) проверява дали за time секунди могат да се произведат \(\ge M\) продукта. Тя е монотонна (повече време -> повече продукти).

bool check(long long time, int m, const std::vector<int>& machines) {
    long long products = 0;
    for (int speed : machines) {
        products += time / speed;
        if (products >= m) return true;
    }
    return products >= m;
}

long long solve(int m, std::vector<int>& machines) {
    long long left = 0, right = 1e18; // Достатъчно голяма горна граница
    long long ans = right;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (check(mid, m, machines)) {
            ans = mid;
            right = mid - 1; // Пробваме по-малко време
        } else {
            left = mid + 1; // Трябва ни повече време
        }
    }
    return ans;
}

⚡ Алгоритми за сортиране в детайли

1. Бързо сортиране (Quick Sort) - Оптимизации

Класическият Quick Sort може да дегенерира до \(O(N^2)\) при сортиран масив, ако винаги избираме първия/последния елемент за Pivot.

Оптимизация - Random Pivot: Избирането на случаен индекс за Pivot прави вероятността за лош случай астрономически малка.

#include <cstdlib> // за rand()

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low >= high) return;

    // Избор на случаен pivot
    int pivotIndex = low + rand() % (high - low + 1);
    int pivot = arr[pivotIndex];
    std::swap(arr[pivotIndex], arr[high]); // Местим pivot най-отзад

    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);

    quickSort(arr, low, i);
    quickSort(arr, i + 2, high);
}

2. Сортиране чрез сливане (Merge Sort)

За разлика от Quick Sort, Merge Sort винаги работи за \(O(N \log N)\) и е стабилен (запазва реда на равните елементи). Използва се често за броене на инверсии.

void merge(std::vector<int>& arr, int left, int mid, int right) {
    std::vector<int> temp;
    int i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);

    for (int k = 0; k < temp.size(); k++) arr[left + k] = temp[k];
}

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

3. C++ `std::sort`

Вградената функция std::sort (в <algorithm>) използва хибриден алгоритъм (Introsort): 1. Започва с Quick Sort. 2. Ако дълбочината на рекурсията стане прекалено голяма, превключва на Heap Sort (за да гарантира \(O(N \log N)\)). 3. За малки подмасиви използва Insertion Sort (защото е по-бърз за малко \(N\)).

🏁 Заключение и Съвети

Винаги използвайте std::sort, освен ако нямате специфична причина (напр. броене на инверсии с Merge Sort).
За задачи с търсене на "минималното X, за което е изпълнено...", винаги мислете за Binary Search on Answer.
Внимавайте с типовете данни (long long) при двоичното търсене, за да избегнете препълване при left + right.