- 1. Time complexity и примеры
- 2. Master's Theorem
- 3. Сортировки
- 4. Data Structures
- 5. Randomized Algorithms
- 6. Hoare Algorithm
- 7. Median of Medians
Time complexity — это оценка того, как растёт время работы алгоритма при увеличении входных данных. Нас интересует асимптотическое поведение при больших n.
Обычно time complexity записывают через Big O. Для определения асимптотики мы всегда берём худший случай и отбрасываем константы и незначащие слагаемые.
Общий алгоритм как считать time complexity:
- Считаешь, сколько раз выполняется код
- Выражаешь это через n
- Берёшь самый быстрорастущий член
- Записываешь Big O
- Обычный:
for (int i = 0; i < n; i++) {
// O(1)
}тело выполняется n раз ⮕ сложность: O(n)
- Два вложенных цикла:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// O(1)
}
}внешний: n, внутренний: n, всего: n * n ⮕ O(n²)
- Внутренний зависит от внешнего:
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
}
}Количество итераций:
0 + 1 + 2 + ... + (n-1) = n(n-1)/2. Асимптотически это n² ⮕ O(n²)
- Три вложенных цикла:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)n * n * n ⮕ O(n³)
- Последовательные циклы:
for (int i = 0; i < n; i++) {
}
for (int j = 0; j < n; j++) {
}n + n = 2n ⮕ O(n)
Асимптотика while ничем не отличается от for
- Обычный:
int i = 0;
while (i < n) {
i++;
}выполняется n раз ⮕ O(n)
- while с делением:
while (n > 1) {
n /= 2;
}Сколько раз делим n на 2, пока не станет 1? log₂(n) ⮕ O(log n)
for (int i = 0; i < n; i++) { // O(n)
while (j > 1) { // O(log n)
j /= 2;
}
}n * log n ⮕ O(n log n)
if (x > 0) {
// O(n)
} else {
// O(1)
}Берём худший случай ⮕ O(n)
Линейная рекурсия
void f(int n) {
if (n == 0) return;
f(n - 1);
}вызывается n раз ⮕ O(n)
| Код | Сложность |
|---|---|
| Один цикл | O(n) |
| Два вложенных | O(n²) |
| Деление на 2 | O(log n) |
| Цикл + лог | O(n log n) |
| Константа | O(1) |
- while внутри for внутри if
for (int i = 0; i < n; i++) { // O(n)
if (i == 0) {
while (j > 1) { // O(log n)
j /= 2;
}
} else {
for (int k = 0; k < n; k++) { // O(n)
}
}
}Берем худший случай: ветка else → O(n) и внешний for → O(n) ⮕ O(n²)
- if внутри while внутри for
for (int i = 0; i < n; i++) { // O(n)
int j = n;
while (j > 1) { // O(log n)
if (j % 2 == 0) {
// O(1)
}
j /= 2;
}
}O(n log n)
- while внутри if, но с ловушкой
for (int i = 0; i < n; i++) {
if (i == 0) { // выполнится 1 раз!
while (j > 1) { // O(log n)
j /= 2;
}
}
}while выполняется 1 раз, остальное — константа ⮕ O(n)
- Все в перемешку
for (int i = 0; i < n; i++) {
int j = i;
while (j > 0) {
if (j % 2 == 0) {
j /= 2;
} else {
j--;
}
}
}O(n²)
Иногда рекурсию можно представить как
Тогда, сложность алгоритма оценивается в 3 случаях:
-
$O(n^d)$ , если$d > log_ba$ -
$O(n^dlog_bn)$ , если$d = log_ba$ -
$O(n^{log_ba})$ , если$d < log_ba$
Идея:
- Считаем, что первые k элементов отсортированы
- Берём следующий элемент и вставляем в правильное место
- Хорошо для почти отсортированных массивов
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
return arrTime complexity:
Идея:
- Проходим по массиву, сравниваем соседние элементы
- Меняем их местами, если порядок неправильный
- Повторяем, пока массив не отсортирован
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arrTime complexity:
Идея:
- Находим минимальный элемент
- Меняем его с первым, потом со вторым, и так далее
- Всегда делает O(n²) сравнений
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]
return arrTime complexity:
Идея:
- Разделяем массив на две половины
- Сортируем рекурсивно каждую половину
- Сливаем две отсортированные части
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Merge
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:]
merged += right[j:]
return mergedTime complexity:
Идея:
- Строим кучу: Проходим по массиву и для каждого элемента вызываем
$insert(x)$ - Извлекаем корень: Забираем значение из
$H[0]$ — это наш текущий минимум.. - Восстанавливаем структуру: На место
$H[0]$ ставим самый последний элемент кучи$H[n-1]$ и вызываем$sift$ $down(0)$ , чтобы этот элемент встал на свое место. - Повторяем: Делаем так
$n$ раз, пока не вытащим все элементы в порядке возрастания.
def heap_sort(arr):
heap = MinHeap()
result = []
# Фаза 1: построение кучи (n вставок)
for x in arr:
heap.insert(x)
# Фаза 2: n извлечений минимума
while heap.heap:
result.append(heap.remove_min())
return resultTime complexity:
Идея:
- Выбираем случайный опорный элемент
$x$ - Разбиваем массив на три части: меньше
$x$ , равные$x$ и больше$x$ - Рекурсивно сортируем части с меньшими и большими элементами
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
x = random.choice(arr)
less = [i for i in arr if i < x]
equal = [i for i in arr if i == x]
greater = [i for i in arr if i > x]
return quick_sort(less) + equal + quick_sort(greater)Time complexity:
Идея:
- Создаем вспомогательный массив C размером
$m$ (диапазон чисел), где индекс соответствует значению элемента. - Проходим по исходному массиву и считаем, сколько раз встретилось каждое число.
- Затем просто выписываем числа по порядку согласно их количеству.
def counting_sort(a):
m = max(a)
n = len(a)
c = [0] * (m + 1)
for x in a:
c[x] += 1
a_prime = []
for value in range(len(c)):
a_prime.extend([value] * c[value])
return a_primeTime complexity:
Если числа большие (например, до
- Представить каждое число
$a_i$ как пару координат$(x_i, y_i)$ . Где$x_i = \lfloor a_i / n \rfloor$ и$y_i = a_i \pmod n$ (остаток от деления). - Дважды применяем Counting Sort. Сначала сортируем по «младшему» разряду (
$y_i$ ), затем по «старшему» ($x_i$ ).
def radix_sort_n2(a):
n = len(a)
def counting_sort_for_radix(arr, getter):
count = [0] * n
for x in arr:
count[getter(x)] += 1
for i in range(1, n):
count[i] += count[i-1]
res = [0] * len(arr)
for x in reversed(arr):
digit = getter(x)
count[digit] -= 1
res[count[digit]] = x
return res
a = counting_sort_for_radix(a, lambda val: val % n)
a = counting_sort_for_radix(a, lambda val: val // n)
return aTime complexity:
Быстрый поиск элемента в уже отсортированном массиве. Идея:
- Берем границы
$l=0$ и$r=n-1$ . - Находим середину
$m = (l + r) / 2$ . - Если искомое число больше того, что в середине, отбрасываем левую половину (
$l = m + 1$ ). Иначе отбрасываем правую ($r = m$ ).
def binary_search(a, x):
l = 0
r = len(a) - 1
while r - l >= 1:
m = (l + r) // 2
if a[m] < x:
l = m + 1
else:
r = m
if a[l] == x:
return l
return -1RAM-модель, что расшифровывается как Random Access Machine, это математическая модель компьютера, в которой все базовые операции выполняются за константное время и используется память со случайным доступом (т. е. к любой ячейке можно обратиться за одинаковое время), чтобы удобно анализировать алгоритмы.
Array (он же массив) это базовая структура данных, представляющая собой упорядоченный набор элементов одного типа, расположенных последовательно в памяти. Каждый элемент имеет индекс, размер задаётся при создании и не меняется, все элементы имеют один тип.
Чтение (return
Heap (она же куча) это структура данных, которая хранит набор элементов
Binary heap, все операции работают за
Кучу удобно хранить в обычном массиве, заполняя элементами сверху вниз, слева направо:
- Корень в
$H[0]$ - Левый ребенок узла
$i$ :$2i + 1$ - Правый ребенок узла
$i$ :$2i + 2$ - Родитель узла
$i$ :$(i - 1) // 2$
Операции:
- Insert (Sift Up / Всплытие)
- Новый элемент
$x$ ставится в самый конец массива (в последний свободный лист). - Пока он меньше своего родителя, мы меняем их местами (swap).
- Элемент «всплывает» вверх до нужной позиции.
Так как высота дерева
$\approx \log n$ , значит максимум$\log n$ обменов.
- Remove Min (Sift Down / Погружение)
- Минимум всегда корень, сохраняем, чтобы вернуть в конце как ответ. Но теперь там пустое место
- Чтобы структура дерева не развалилась, мы берем самый последний элемент из массива и ставим его на место корня.
- Теперь этот большой элемент должен спуститься на свое место: выбираем меньшего из двух детей, если наш элемент больше мина, свапаем их
- Повторяем процесс, пока не найдет своего места
Входные данные подаются в алгоритм при помощи генератора случайных чисел. Исход может меняться от запуска к запуску.
Среднее время:
Худшее среднее:
Задача: найти элемент, который стоял бы на
import random
def quick_select(arr, k):
def select(left, right, k_idx):
if left == right:
return arr[left]
pivot_idx = partition(left, right)
if k_idx == pivot_idx:
return arr[k_idx]
elif k_idx < pivot_idx:
return select(left, pivot_idx - 1, k_idx)
else:
return select(pivot_idx + 1, right, k_idx)
def partition(left, right):
rand_idx = random.randint(left, right)
arr[rand_idx], arr[right] = arr[right], arr[rand_idx]
x = arr[right]
i = left
for j in range(left, right):
if arr[j] <= x:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[right] = arr[right], arr[i]
return i
return select(0, len(arr) - 1, k)Time complexity:
Идея:
- Разбиваем массив на группы по 5 элементов.
- Находим медиану в каждой группе (сортировкой 5 элементов).
- Рекурсивно находим медиану среди полученных медиан — это наш опорный элемент
$x$ . - Используем
$x$ для разделения массива (partition) и продолжаем поиск в нужной части.
def get_median(sub_arr):
return sorted(sub_arr)[len(sub_arr) // 2]
def median_of_medians(arr, k):
if len(arr) <= 5:
return sorted(arr)[k]
subgroups = [arr[i:i + 5] for i in range(0, len(arr), 5)]
medians = [get_median(group) for group in subgroups]
x = median_of_medians(medians, len(medians) // 2)
less = [i for i in arr if i < x]
equal = [i for i in arr if i == x]
greater = [i for i in arr if i > x]
m = len(less)
e = len(equal)
if k < m:
return median_of_medians(less, k)
elif k < m + e:
return x
else:
return median_of_medians(greater, k - m - e)Time complexity: