Введение
Как измерять эффективность алгоритма
Короткое повторение основ из §2.1–2.2 Левитина. Без него модули не читаются: всё дальнейшее — это подсчёт одной операции как функции от размера входа.
Размер входа
Почти любой алгоритм работает дольше на больших входах. Поэтому эффективность записывают как функцию от параметра $n$ — размера входа.
- Сортировка, поиск, максимум массива: $n$ — число элементов.
- Перемножение матриц $n\times n$: обычно порядок $n$. Можно взять и число элементов $N = n^2$, но тогда тот же алгоритм получит другой класс (см. задачу A3).
- Вход — одно число $n$ (проверка простоты): размер — число битов $$b = \lfloor \log_2 n \rfloor + 1.$$ Значение $n$ при этом растёт экспоненциально от $b$.
Иногда параметров несколько: у графа — число вершин и число рёбер.
Базовая операция
Считать время в секундах неудобно: оно зависит от компьютера, компилятора и качества программы. Вместо этого выбирают базовую операцию — ту, что вносит наибольший вклад во время работы, — и считают, сколько раз она выполняется. Обычно это самая затратная операция во внутреннем цикле: сравнение ключей при сортировке и поиске, умножение в матричных алгоритмах.
Если $c_{op}$ — время одной базовой операции, а $C(n)$ — число её выполнений, то
$$T(n) \approx c_{op}\, C(n).$$Формула приближённая, но позволяет отвечать на вопросы об отношениях. Пусть $C(n) = \tfrac12 n(n-1) \approx \tfrac12 n^2$ при больших $n$. Во сколько раз дольше алгоритм будет работать на вдвое большем входе?
$$\frac{T(2n)}{T(n)} \approx \frac{c_{op}\cdot\tfrac12(2n)^2}{c_{op}\cdot\tfrac12 n^2} = 4.$$И $c_{op}$, и множитель $\tfrac12$ сократились. Поэтому анализ игнорирует постоянные множители и следит только за порядком роста.
Порядок роста
На маленьких входах разница между алгоритмами почти не видна. Она проявляется при больших $n$, и определяет её порядок роста функции $C(n)$.
| $n$ | $\log_2 n$ | $n\log_2 n$ | $n^2$ | $n^3$ | $2^n$ |
|---|---|---|---|---|---|
| $10$ | $3{,}3$ | $3{,}3\cdot10^1$ | $10^2$ | $10^3$ | $10^3$ |
| $10^2$ | $6{,}6$ | $6{,}6\cdot10^2$ | $10^4$ | $10^6$ | $1{,}3\cdot10^{30}$ |
| $10^3$ | $10$ | $1{,}0\cdot10^4$ | $10^6$ | $10^9$ | |
| $10^6$ | $20$ | $2{,}0\cdot10^7$ | $10^{12}$ | $10^{18}$ |
Удобно запомнить, как функции реагируют на удвоение $n$: $\log_2 n$ растёт на 1, $n$ — вдвое, $n\log n$ — чуть больше чем вдвое, $n^2$ — вчетверо, $n^3$ — в 8 раз, а $2^n$ возводится в квадрат. Алгоритмы с экспоненциальным числом операций применимы только к очень маленьким входам. Интерактивный график — в модуле 1.
Основание логарифма на порядок роста не влияет: $\log_a n = \log_a b \cdot \log_b n$ отличается от $\log_b n$ постоянным множителем. Поэтому пишут просто $\log n$.
Нотации O, Ω, Θ
Ниже $t(n)$ — число операций алгоритма, $g(n)$ — простая функция для сравнения, обе неотрицательны.
$O$ (сверху). $t(n) \in O(g(n))$, если существуют $c > 0$ и $n_0 \ge 0$ такие, что $t(n) \le c\,g(n)$ для всех $n \ge n_0$. Подробнее: O-нотация.
$\Omega$ (снизу). $t(n) \in \Omega(g(n))$, если $t(n) \ge c\,g(n)$ для всех $n \ge n_0$ при некоторых $c > 0$, $n_0$. Подробнее: Ω-нотация.
$\Theta$ (точно). $t(n) \in \Theta(g(n))$, если $c_2\,g(n) \le t(n) \le c_1\,g(n)$ для всех $n \ge n_0$. Подробнее: Θ-нотация.
Как не перепутать: $O$ — «растёт не быстрее», $\Omega$ — «растёт не медленнее», $\Theta$ — «растёт так же». $\Theta$ означает $O$ и $\Omega$ одновременно. Пример для $t(n) = 3n^2 + 5$:
| $g(n) = n$ | $g(n) = n^2$ | $g(n) = n^3$ | |
|---|---|---|---|
| $t \in O(g)$? | нет | да | да |
| $t \in \Omega(g)$? | да | да | нет |
| $t \in \Theta(g)$? | нет | да | нет |
Поэтому запись $3n^2 + 5 \in O(n^3)$ верна, но малоинформативна; точный ответ даёт $\Theta(n^2)$. В разборах мы ищем именно $\Theta$.
Пример доказательства по определению: $\tfrac12 n(n-1) \in \Theta(n^2)$. Сверху: $\tfrac12 n^2 - \tfrac12 n \le \tfrac12 n^2$ при $n \ge 0$. Снизу: при $n \ge 2$ имеем $\tfrac12 n \le \tfrac14 n^2$, поэтому $\tfrac12 n^2 - \tfrac12 n \ge \tfrac14 n^2$. Подходят $c_1 = \tfrac12$, $c_2 = \tfrac14$, $n_0 = 2$.
На практике удобнее сравнивать через предел:
$$\lim_{n\to\infty}\frac{t(n)}{g(n)} = \begin{cases} 0 & t \text{ растёт медленнее: } t \in O(g),\\ c > 0 & \text{одинаковый порядок: } t \in \Theta(g),\\ \infty & t \text{ растёт быстрее: } t \in \Omega(g).\end{cases}$$Если алгоритм состоит из двух частей, выполняемых друг за другом, общий порядок определяет худшая часть:
$$t_1 \in O(g_1),\ t_2 \in O(g_2) \ \Rightarrow\ t_1 + t_2 \in O(\max\{g_1, g_2\}).$$Худший, лучший и средний случаи
У многих алгоритмов число операций зависит не только от $n$, но и от конкретного входа. Классический пример — последовательный поиск ключа $K$:
ALGORITHM SequentialSearch(A[0..n − 1], K)
//Ищет K в массиве; возвращает индекс первого совпадения или −1
i ← 0
while i < n and A[i] ≠ K do
i ← i + 1
if i < n return i
else return −1
- Худший случай — вход размера $n$, на котором операций больше всего. Здесь ключа нет или его первое вхождение стоит в последней позиции: $C_{worst}(n) = n$. Оценка худшего случая — гарантия: больше $n$ сравнений не будет никогда.
- Лучший случай — вход размера $n$, на котором операций меньше всего. Здесь ключ первый: $C_{best}(n) = 1$. Лучший случай — это не маленький вход: размер $n$ зафиксирован, выбирается только содержимое.
- Средний случай — ожидаемое число операций на «случайном» входе. Для него нужны явные вероятностные допущения. Он не равен среднему арифметическому худшего и лучшего. Полный вывод для последовательного поиска — в модуле 1.
Если число операций одинаково для всех входов размера $n$ (как у поиска максимума), три случая совпадают, и их не различают.
Что дальше
Модуль 1 учит считать операции в алгоритмах с циклами: число операций записывается суммой. Модуль 2 — алгоритмы с рекурсией: число операций записывается рекуррентным соотношением. В обоих модулях используется один и тот же план из пяти шагов.
Входной квиз
Пять вопросов о том, что нужно знать перед модулями. После выбора варианта появляются объяснения ко всем вариантам.