Сортировки целых чисел, порядковые статистика, V.E.B. (8 октября 2024)

1. Забытое с прошлой пары: Сравнение трёх решений задачи о пересечении множеств
   1. Решение хеш-таблицей: Θ(n), доппамять, большая константа
      1. Сортировка + бинпоиск: O(sort) + O(nlogn), sort, lower_bound, минимум кода
      2. Два указателя: O(sort) + O(n), малая константа
   
   
2. [20 минут] Quick-Sort (повторение, доппамять)
   1. Сколько памяти? Версия с O(logn) доп памяти в худшем случае.
   2. [10 минут] Повторение оценки времени #1: мы считаем среднее время = сумма по всем рандомам = сумма по всем парам
   3. [5 минут] Повторение оценки времени #2: напоминаем историю про интеграл
   
   
3. [20 минут] Порядковые статистика за O(n)
   1. QSort = get x + partition x + QSort + QSort, избавимся от одной ветки
   2. [10 минут] Одноветочный QuickSort. Время работы. Простая версия, дающая асимптотику; сложная с константой 4, как упражнение.
   3. [10 минут] Детерминированный partition.
   4. C++: nth_element, partition

1. [5 минут] Целочисленные сортировки
   1. Почему вообще числа можно сортировать быстрее?
   2. Count Sort за O(n+m). Замечание: стабильность.
2. [15 минут] Radix sort.
   1. Сортируем пары подсчётом за O(n+m)
   2. Сортируем вектора за O(n×len)
   3. Сортируем числа за O(nlog_nm)
3. [20 минут] Bucket Sort
   1. Алгоритм: if (Min != Max) разбить на n бакетов, вызваться для каждого
   2. Вариации: для каждого вызваться рекурсивно (BB), для каждого вызвать insertion sort (BI)
   3. Lm #0: MAX-MIN ≤ n ⇒ BI = Θ(n), BB = Θ(n)
   4. Lm #1: на равномерном распределении матожидание времние BI работает за O(n). Оценим ∑k_i²
   5. Lm #2: BB работает в худшем за O(n log(MAX-MIN))

1. [15 минут] V.E.B за loglogC
   1. Сформулируем задачу: heap для целых чисел от 0 до C-1. C = 2^2k (чисел битовой длины 2^k).
   2. Интерфейс Min = O(1), Add и Del = O(k) = O(loglogC).
   3. Случаи: size = 0, size = 1, size ≥ 2, struct Heapk: { Heapk-1 a; u_map<int,Heapk-1> b; int min, size; }.
   4. Реализуем Add, пересчёт Min
   5. Реализуем Del