АиСД L03 - Решето Эратосфена и квадратичные сортировки

О чём лекция

Две темы. Первая — решето Эратосфена: все простые числа до N сразу, за $O(N\log \log N)$ вместо проверки каждого числа по отдельности. Вторая — сортировка: что это такое, по каким свойствам сравнивают сортировки (время, память, устойчивость) и три простейших алгоритма — выбором, вставками и пузырьком. Все три работают за $O(N^2)$; в следующей лекции это станет поводом искать быстрее.

Как читать

Доказательства в блоках «Не из лекции» дописаны к конспекту: на лекции их не было. Всё остальное — с доски.

Маршрут

1. Все простые до N → Решето Эратосфена
2. Что такое сортировка и чем сортировки отличаются → Сортировка
3. Выбором, вставками, пузырьком → Квадратичные сортировки
4. Как записывать оценки → Асимптотические оценки, Время работы алгоритма

Запись a ... b в псевдокоде

На досках не уточняется, входит ли правая граница. Смотреть надо по смыслу. В решете for d = 2 ... N граница входит: массив на $N+1$ элемент, и число N тоже надо проверить. В сортировках for i = 0 ... N граница не входит — это полуинтервал $[0,N)$, индексы массива из N элементов. Иначе пузырёк с его arr[j+1] при j = 0 ... N−i−1 вышел бы за массив уже на первом проходе.

1. Решето Эратосфена

Задача. N — натуральное число. Найти все простые $p\le N$.

Простое: $p\in \mathbb{N}$, и $p$ делится только на $p$ и на 1 — и всё.

Идея алгоритма

Выписываем числа от 0 до N и отмечаем: ✓ — простое, ✗ — нет.

 0  1  2  3  4  5  6  7  8  9  10 11 12 13 ... N
 ✗  ✗  ✓  ✓  ✗  ✓  ✗  ✓  ✗  ✗  ✗  ✓  ✗  ✓ ...

• 0 и 1 — не простые.
• Идём по числам $d$ слева направо:
  • $d$ не простое (✗) — пропускаем;
  • $d$ простое (✓) — вычёркиваем $d\cdot m$, где $m$ перебираем.

Алгоритм

is_prime = [T, T, ..., T]              // N + 1 элемент
is_prime[0] = is_prime[1] = F
for d = 2 ... N
    если is_prime[d] = T               // d — простое
        m = 2
        while (m * d ≤ N)
            is_prime[m * d] = F
            m++
for d = 2 ... N
    если is_prime[d] = T
        print(d)

Асимптотика (без доказательства): $T(N)=O(N\log \log N)$.

Не из лекции: почему вычеркнуты ровно составные

Утверждение: после первого цикла is_prime[k] = T ⇔ $k$ простое, для всех $0\le k\le N$.

Простое не вычёркивается. Вычёркиваются только числа вида $m\cdot d$, где $m\ge 2$ и $d\ge 2$. У такого числа есть делитель $d$, отличный от 1 и от самого числа, — оно составное.

Составное вычёркивается. Пусть $k\le N$ составное, $d$ — его наименьший делитель, больший 1. Он простой: иначе у него самого был бы делитель меньше, и этот делитель делил бы $k$. Значит, is_prime[d] никто не вычеркнет, и когда цикл дойдёт до $d$, проверка пройдёт. Тогда $m$ переберёт $2,3,\dots$ и дойдёт до $m=k/d\ge 2$: $m\cdot d=k\le N$. Число $k$ вычеркнуто. ∎

Тонкость. Проверка is_prime[d] = T смотрит в таблицу, которую алгоритм ещё строит. Это законно: если $d$ составное, его наименьший простой делитель меньше $d$ и уже обработан — $d$ к этому моменту вычеркнуто.

Не из лекции: сначала грубая оценка $O(N\log N)$

Для простого $d$ внутренний цикл делает $\lfloor N/d\rfloor -1\le N/d$ шагов. Остальное — два прохода по $d$, это $O(N)$. Если завысить и считать, что внутренний цикл работает для каждого $d$, получится

${\sum }_{d=2}^N\frac{N}{d}=N\left(\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{N}\right)\le N\ln N.$

Последнее — оценка суммы гармонического ряда: $\frac{1}{d}\le {\int }_{d-1}^d\frac{dx}{x}$, поэтому сумма не больше ${\int }_1^N\frac{dx}{x}=\ln N$. Итого $O(N\log N)$ — уже сильно лучше, чем проверять каждое число до корня, $O(N\sqrt{N})$.

Не из лекции: откуда $\log \log N$

На самом деле внутренний цикл работает только для простых $d$, и

$T(N)=O\left(N+N{\sum }_{p\le N}\frac{1}{p}\right).$

Осталось доказать, что ${\sum }_{p\le N}\frac{1}{p}=O(\log \log N)$. Три шага.

Шаг 1. Произведение простых до $n$ не больше $4^n$. Индукция по $n$. При $n=1,2$ верно. Чётное $n>2$ не простое, произведение такое же, как для $n-1$. Нечётное $n=2m+1$: каждое простое $p$ из $(m+1,2m+1]$ делит числитель $\left(\genfrac{}{}{0ex}{}{2m+1}{m}\right)=\frac{(2m+1)!}{m!(m+1)!}$ и не делит знаменатель, поэтому их произведение делит $\left(\genfrac{}{}{0ex}{}{2m+1}{m}\right)$. А $\left(\genfrac{}{}{0ex}{}{2m+1}{m}\right)=\left(\genfrac{}{}{0ex}{}{2m+1}{m+1}\right)$, оба слагаемых входят в ${\sum }_k\left(\genfrac{}{}{0ex}{}{2m+1}{k}\right)=2^{2m+1}$, значит, $\left(\genfrac{}{}{0ex}{}{2m+1}{m}\right)\le 4^m$. По предположению индукции произведение простых до $m+1$ не больше $4^{m+1}$. Всего — не больше $4^{m+1}\cdot 4^m=4^{2m+1}$.

Логарифмируя: ${\sum }_{p\le n}\ln p\le n\ln 4$.

Шаг 2. ${\sum }_{p\le n}\frac{\ln p}{p}\le \ln n+\ln 4$. Среди чисел $1,\dots ,n$ на $p$ делятся $\lfloor n/p\rfloor$ штук, поэтому $n!$ делится на $p^{\lfloor n/p\rfloor }$. Значит,

\ \ge\ \sum_{p \le n} \left(\frac np - 1\right) \ln p \ =\ n \sum_{p \le n} \frac{\ln p}{p} - \sum_{p \le n} \ln p.$$ По шагу 1 последняя сумма не больше $n \ln 4$. Делим на $n$. **Шаг 3. Разбиваем простые на блоки.** Блок $k$ — числа из $[2^{2^k}, 2^{2^{k+1}})$: $[2, 4)$, $[4, 16)$, $[16, 256)$, … Для $p$ из блока $k$ верно $\ln p \ge 2^k \ln 2$, поэтому $\frac1p = \frac{\ln p}{p} \cdot \frac{1}{\ln p} \le \frac{\ln p}{p} \cdot \frac{1}{2^k \ln 2}$. Сумма по блоку, по шагу 2 с $n = 2^{2^{k+1}}$: $$\sum_{p \in \text{блок } k} \frac1p \ \le\ \frac{2^{k+1} \ln 2 + 2 \ln 2}{2^k \ln 2} \ =\ 2 + 2^{1-k} \ \le\ 4.$$ Блоков, в которых есть числа до N, — столько, сколько $k$ с $2^{2^k} \le N$, то есть $k \le \log_2 \log_2 N$. Их не больше $\log_2 \log_2 N + 1$, и $$\sum_{p \le N} \frac1p \le 4 (\log_2 \log_2 N + 1) = O(\log \log N), \qquad T(N) = O(N \log \log N). \ ∎$$ Оценка точная: на самом деле $\sum_{p \le N} \frac1p \approx \ln \ln N + 0{,}26$ (теорема Мертенса, здесь без доказательства). Прогон на $N = 10^8$: внутренний цикл сделал $3{,}09 \cdot 10^8$ шагов, $N \ln \ln N \approx 2{,}91 \cdot 10^8$.

Не из лекции: память

Массив is_prime на $N+1$ элемент: $M(N)=O(N)$. На лекции не записано.

2. Что такое сортировка

Было $a_0,a_1,\dots ,a_N$ — стало $a_{(0)},a_{(1)},\dots ,a_{(N)}$: те же элементы, переставленные.

$\{a_0,a_1,\dots ,a_N\}=\{a_{(0)},a_{(1)},\dots ,a_{(N)}\}$

Упорядоченно, например: $a_{(0)}<a_{(1)}<\cdots <a_{(N)}$. Виды порядка:

1. возрастание: $a_{(0)}<a_{(1)}<\cdots <a_{(N)}$;
2. неубывание: $a_{(0)}\le a_{(1)}\le \cdots \le a_{(N)}$;
3. убывание: $a_{(0)}>a_{(1)}>\cdots >a_{(N)}$;
4. невозрастание: $a_{(0)}\ge a_{(1)}\ge \cdots \ge a_{(N)}$.

Применение: фильтры, маркетплейсы, бинарный поиск (Бинарный поиск работает только на отсортированном массиве).

Не из лекции: строго или нестрого

Если в массиве есть равные элементы, расставить их по строгому возрастанию нельзя — только по неубыванию. Поэтому «отсортировать по возрастанию» на практике значит по неубыванию: все алгоритмы ниже сравнивают строго (>, <) и равные оставляют рядом.

Подробнее — Сортировка.

3. Свойства сортировок

• Время выполнения $T(N)$.
• Дополнительная память $M(N)$ — см. Время работы алгоритма.
• Устойчивость (стабильность) сортировки.

Пример: $[1,2,1]\to [1,1,2]$. Пометим единицы, чтобы их различать:

Устойчивая	Неустойчивая
$[\dot{1},2,\ddot{1}]\to [\dot{1},\ddot{1},2]$	$[\dot{1},2,\ddot{1}]\to [\ddot{1},\dot{1},2]$
порядок одинаковых элементов сохранён	порядок одинаковых поменялся

Не из лекции: зачем нужна устойчивость

Для чисел разница не видна: две единицы неотличимы. Она важна, когда сортируют записи по ключу. Пусть товары уже отсортированы по цене, и теперь их сортируют по рейтингу. Устойчивая сортировка оставит товары с одинаковым рейтингом в порядке цены, неустойчивая — перемешает.

4. Тривиальный алгоритм

[ неотсортированный ]  ──▶  [ отсортированный ]

1. Рандомно переставляем элементы массива — $O(1)$.
2. Проверяем, что arr отсортирован — $O(N)$.

Перестановок $N!$, отсюда $T(N)=O(N\cdot N!)$.

Не из лекции: поправки к оценке

• Случайная перестановка стоит $O(N)$, а не $O(1)$: надо переставить каждый из N элементов. На итог не влияет — попытка всё равно стоит $O(N)+O(N)=O(N)$.
• $O(N\cdot N!)$ — среднее, а не худшее время. Если все элементы разные, отсортированная перестановка одна из $N!$, и каждая попытка попадает в неё с вероятностью $1/N!$. В среднем нужно $N!$ попыток — отсюда $N\cdot N!$. Но ничто не мешает не попасть ни разу за миллиард попыток: гарантированного времени у алгоритма нет.
• Масштаб: $10!\approx 3,6\cdot 10^6$, $20!\approx 2,4\cdot 10^{18}$. Уже на двадцати элементах — десятки лет при $10^8$ операций в секунду.

5. Поиск максимума

arr = [ ... ]
mx = arr[0]
for i = 0 ... N
    если arr[i] > mx
        mx = arr[i]

[////////////////|▮|           ]
 └──── mx ──────┘ arr[i]

$T(N)=O(N)$, $M(N)=O(1)$.

Не из лекции: почему ответ верный

Инвариант: перед шагом $i$ значение mx — максимум среди arr[0], …, arr[i−1] (на рисунке — заштрихованная часть). Шаг сравнивает arr[i] с этим максимумом и, если нужно, обновляет его. После последнего шага mx — максимум всего массива.

Оптимизация: MAX → arr[0]

Не храним максимум в отдельной переменной, а держим его на месте arr[0]:

arr = [ ... ]
for i = 0 ... N
    если arr[i] > arr[0]
        swap(arr[i], arr[0])

swap — обмен двух элементов через временную переменную:

t = arr[0]
arr[0] = arr[i]
arr[i] = t

Не из лекции: зачем это

После цикла максимум стоит в arr[0], а массив по-прежнему содержит те же элементы — переставленные. Это ровно один шаг сортировки: поставить на первое место нужный элемент. Сортировка выбором ниже повторяет этот шаг для каждой позиции — только ищет минимум.

Почему без t нельзя: после arr[0] = arr[i] старое значение arr[0] потеряно, и arr[i] = arr[0] запишет в arr[i] его же собственное значение.

6. Сортировка выбором (Selection Sort)

По возрастанию: первые $i$ позиций уже на месте, в остатке ищем минимум и ставим его следующим.

[▨|▨|▨ ... ▨|        ...        ]
 └──── i ────┘└── поиск мин ──┘

На полях — столбики по высоте: слева $k$ самых маленьких, уже по порядку, справа — вперемешку.

for i = 0 ... N
    for j = i ... N
        если arr[i] > arr[j]
            swap(arr[i], arr[j])

$T(N)=O(N^2)$, $M(N)=O(1)$. Устойчивая: нет.

$[\dot{2},\ddot{2},1]\to [1,\ddot{2},\dot{2}]$

Подробно о всех трёх сортировках — Квадратичные сортировки.

Не из лекции: доказательство правильности

Инвариант внешнего цикла: перед шагом $i$ элементы arr[0], …, arr[i−1] — это $i$ наименьших элементов массива, по неубыванию.

Внутренний цикл ставит в arr[i] минимум остатка. После проверки очередного $j$ в arr[i] лежит минимум из arr[i], …, arr[j]: если arr[j] меньше текущего arr[i], их меняют местами. Обмены идут только внутри arr[i], …, arr[N−1], так что остаток содержит те же элементы. После $j=N-1$ в arr[i] — минимум остатка.

Этот минимум не меньше любого из первых $i$ элементов (они наименьшие), и не больше любого из оставшихся. Префикс удлинился на один элемент и остался упорядоченным. После $i=N-1$ отсортирован весь массив. ∎

Не из лекции: точное число сравнений

Внутренний цикл на шаге $i$ делает $N-i$ сравнений (при $j=i$ — сам с собой, лишнее, но так на доске). Всего

${\sum }_{i=0}^{N-1}(N-i)=N+(N-1)+\cdots +1=\frac{N(N+1)}{2}=\Theta (N^2)$

— на любом входе, даже на уже отсортированном: цикл не знает, что минимум уже на месте. Прогон на $N=1000$: 500 500 сравнений.

Не из лекции: почему неустойчива

Обмен arr[i] с далёким arr[j] перебрасывает arr[i] через все элементы между ними — в том числе через равный ему. Разбор примера:

• $i=0$: $j=1$ — $\dot{2}>\ddot{2}$? нет; $j=2$ — $\dot{2}>1$? да, обмен: $[1,\ddot{2},\dot{2}]$. Двойка $\dot{2}$ перепрыгнула через $\ddot{2}$.
• $i=1$: $\ddot{2}>\dot{2}$? нет. Порядок двоек так и остался обратным.

Прогон на C++ даёт то же самое.

Не из лекции: на доске — не классический вариант

На доске swap выполняется внутри внутреннего цикла, каждый раз, как нашёлся элемент меньше arr[i]. Классическая сортировка выбором сначала находит индекс минимума и делает один обмен на шаг $i$. Сравнений столько же, $\Theta (N^2)$, обменов — не больше $N-1$ вместо $O(N^2)$. Классический вариант тоже неустойчив, контрпример тот же.

7. Сортировка вставками (Insertion Sort)

По возрастанию: левая часть уже отсортирована, очередной элемент «проваливается» влево, пока слева от него элемент больше.

[//////////////|▮|          ]
          ←────┘ j

arr = [ ... ]
for i = 0 ... N
    j = i + 1
    while (j > 0 и arr[j] < arr[j−1])
        swap(arr[j], arr[j−1])
        j = j − 1

$T(N)=O(N^2)$, $M(N)=O(1)$. Устойчивость: да. На рисунке — два одинаковых столбика рядом: равные элементы друг через друга не перепрыгивают.

Выход за границу массива

При $i=N-1$ (последняя итерация полуинтервала $[0,N)$) получается j = N, и условие while читает arr[N] — за пределами массива. В C++ это Неопределённое поведение; прогон с AddressSanitizer сообщает heap-buffer-overflow. Внешний цикл должен идти на одну итерацию меньше: for i = 0 ... N−1. Или, как чаще пишут: for i = 1 ... N, j = i.

Не из лекции: доказательство правильности

Инвариант: перед шагом $i$ отсортированы arr[0], …, arr[i]. Вначале это один элемент — отсортирован.

Шаг вставляет arr[i+1]. Пока он строго меньше левого соседа, они меняются местами. Цикл останавливается в одном из двух случаев:

• $j=0$ — элемент меньше всех, стоит первым;
• arr[j−1] ≤ arr[j] — слева всё не больше его.

Справа от него стоят элементы, через которые он прошёл, — они больше его и по-прежнему упорядочены (каждый сдвинулся на одну позицию вправо). Значит, arr[0], …, arr[i+1] отсортированы. ∎

Не из лекции: сколько обменов

Инверсия — пара позиций $p<q$, где arr[p] > arr[q]. Обмен двух соседних элементов, стоящих в неправильном порядке, убирает ровно одну инверсию и других не трогает. Значит, обменов ровно столько, сколько инверсий во входе.

• Худший случай — массив по убыванию: инверсий $\frac{N(N-1)}{2}$, это $\Theta (N^2)$.
• Лучший — уже отсортированный: обменов нет, на каждом шаге одно сравнение, всего $N-1$, это $O(N)$.

Прогон на $N=1000$: по убыванию — 499 500 сравнений, по возрастанию — 999. В отличие от выбора, вставки работают быстро на почти отсортированных данных.

Не из лекции: почему устойчива

Обмен происходит только при строгом arr[j] < arr[j−1]. Элемент останавливается перед первым равным ему и никогда не перепрыгивает через него. Элементы движутся только обменом соседей, поэтому равные не могут поменяться местами иначе как напрямую — а напрямую их не меняют. Если написать ≤, сортировка останется правильной, но станет неустойчивой.

8. Сортировка пузырьком (Bubble Sort)

Каждый проход «всплывает» максимум: он уезжает вправо, на позицию $N-i$. Справа копится отсортированная часть.

[ ~~~~~ max ~~~~~▶|▮|//////////]
                N−i └─── i ───┘

for i = 0 ... N
    for j = 0 ... N−i−1
        если arr[j] > arr[j+1]
            swap(arr[j], arr[j+1])

$T(N)=O(N^2)$, $M(N)=O(1)$. Устойчивость: да.

Не из лекции: доказательство правильности

Утверждение о проходе. Во время прохода $i$ после сравнения на шаге $j$ в arr[j+1] лежит максимум из arr[0], …, arr[j+1]. Индукция по $j$: если arr[j] — максимум первых $j+1$ элементов и он больше arr[j+1], обмен утащит его вправо; если не больше — максимум и так arr[j+1].

Инвариант внешнего цикла: после прохода $i$ последние $i+1$ позиций занимают $i+1$ наибольших элементов, по неубыванию. Проход $i$ заканчивается на $j=N-i-2$ и приносит в arr[N−i−1] максимум неотсортированной части. Он не больше уже стоящих справа — те наибольшие. ∎

Последний проход $i=N-1$ пустой: j = 0 ... −1.

Не из лекции: число сравнений и устойчивость

Сравнений ${\sum }_{i=0}^{N-1}(N-i-1)=\frac{N(N-1)}{2}=\Theta (N^2)$ на любом входе. На доске оценка записана символом, похожим на $\Omega$; верны обе, точный порядок — $\Theta (N^2)$.

Обменов, как и у вставок, ровно столько, сколько инверсий: каждый обмен соседей в неправильном порядке убирает одну.

Устойчива по той же причине, что вставки: меняются только соседи и только при строгом >. Равные соседи остаются как были.

Частая оптимизация: если за проход не было ни одного обмена, массив уже отсортирован, и можно остановиться. Тогда на отсортированном входе — $O(N)$.

Сравнение

	$T(N)$	$M(N)$	Устойчива	Сравнений (не из лекции)
Выбором	$O(N^2)$	$O(1)$	нет	$\frac{N(N+1)}{2}$ всегда
Вставками	$O(N^2)$	$O(1)$	да	от $N-1$ до $\approx \frac{N(N-1)}{2}$
Пузырьком	$O(N^2)$	$O(1)$	да	$\frac{N(N-1)}{2}$ всегда

Проверено прогоном на 2000 случайных массивах с повторами: все три сортируют правильно, неустойчив только выбор.

Грабли

• Сортировка вставками с доски на последней итерации читает arr[N]. Внешний цикл — до N − 1.
• swap без временной переменной теряет одно из значений.
• Запись a ... b не говорит, входит ли b: в решете входит, в сортировках нет. Проверять по индексам.
• Тривиальная сортировка не имеет гарантированного времени — $O(N\cdot N!)$ только в среднем.
• ≤ вместо < во вставках (или ≥ вместо > в пузырьке) ломает устойчивость.

После этой лекции должно получаться

• написать решето Эратосфена и доказать, что вычеркнуты ровно составные;
• объяснить, откуда в решете $\log \log N$ и почему грубая оценка даёт $N\log N$;
• определить сортировку и устойчивость, привести пример неустойчивой;
• написать сортировки выбором, вставками и пузырьком, доказать их через инварианты и посчитать сравнения;
• объяснить, почему выбор неустойчив, а вставки и пузырёк — устойчивы;
• найти выход за границу в сортировке вставками с доски.