АиСД L02 - Простейшие алгоритмы

О чём лекция

Пять простых алгоритмов, на которых отрабатываются оценки из первой лекции: разложение на простые множители, НОД двумя версиями алгоритма Евклида, линейный и бинарный поиск в массиве и бинарный поиск по ответу — на примере квадратного корня. Главная мысль: одна и та же задача решается за $O(N)$ и за $O(\log N)$, и на больших входах это разница между часами и мгновением.

Как читать

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

Маршрут

1. Как оценивать → Асимптотические оценки, Время работы алгоритма
2. НОД → Алгоритм Евклида
3. Поиск в отсортированном массиве и по ответу → Бинарный поиск
4. Дробные числа в поиске → Типы с плавающей точкой

1. Разложение на простые множители

Число делят на наименьший возможный делитель, пока не останется 1. Разбор в столбик — слева число, справа делитель; зачёркнуто то, что не поделилось:

30 | 2            24 | 2
15 | 2  ✗         12 | 2
15 | 3             6 | 2
 5 | 3  ✗          3 | 3
 5 | 4  ✗          1 |
 5 | 5
 1 |

$30=2\cdot 3\cdot 5$, $24=2\cdot 2\cdot 2\cdot 3$.

Алгоритм

Разложить число N на простые множители:

d = 2
while (N ≠ 1)
    если N ⋮ d
        N = N / d
        вывести(d)
    иначе
        d = d + 1

Асимптотика: $T(N)=O(N)$ — линейная, $M(N)=O(1)$.

$M(N)=O(1)$: кроме самого N алгоритм хранит только d, сколько бы ни было N.

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

Когда алгоритм делит на d, у текущего N нет делителей от 2 до $d-1$: каждый такой делитель уже был проверен, и на него поделили, пока делилось.

Пусть выведенное d составное: $d=x\cdot y$, $2\le x<d$. Тогда $N⋮d$ и $d⋮x$, значит $N⋮x$ — а делителей меньше d у N не осталось. Противоречие, значит d простое.

Множители выводятся по неубыванию и с кратностью: $2,2,2,3$ для 24.

Не из лекции: почему алгоритм остановится и почему $O(N)$

Пока $N\ne 1$, у N есть делитель не больше самого N — например, само N. Поэтому d никогда не перерастёт текущее N: на каком-то шаге делитель найдётся, и N уменьшится.

Каждая итерация цикла — либо деление, либо d = d + 1.

• Делений не больше ${\log }_{2}N$: каждое уменьшает N хотя бы вдвое, потому что $d\ge 2$.
• Увеличений d не больше N: d растёт от 2 и не превышает исходное N.

Всего итераций не больше $N+{\log }_{2}N$, это $O(N)$. Оценка достигается: для простого N d проходит все значения от 2 до N — это $N-2$ увеличений и одно деление в конце, $N-1$ итерация.

2. Наибольший общий делитель

Через разложения:

$$24=2\cdot 2\cdot \underline{2\cdot 3},30=\underline{2\cdot 3}\cdot 5,\text{НОД}(24,30)=2\cdot 3=6$$

Определение. $\text{НОД}(a,b)=k$, если $k$ — максимальное число, для которого $a⋮k$ и $b⋮k$.

Раскладывать на множители долго — это $O(N)$ на каждое число. Алгоритм Евклида находит НОД без разложения. Подробнее — Алгоритм Евклида.

3. Алгоритм Евклида: вычитание

Свойства

• $\text{НОД}(a,b)=\text{НОД}(b,a)$;
• $\text{НОД}(a,b)=\text{НОД}(a,b-a)$, если $b\ge a$;
• $\text{НОД}(a,1)=1$; $\text{НОД}(a,0)=a$.

Доказательство второго свойства

На лекции записано начало:

• по определению $\exists k$: $a⋮k$ и $b⋮k$, $k$ — максимальный;
• по определению $\exists k_2$: $a⋮k_2$ и $(b-a)⋮k_2$, $k_2$ — максимальный;
• $(b-a)⋮k_2\iff b⋮k_2$.

Не из лекции: доказательство целиком

Покажем, что у пар $(a,b)$ и $(a,b-a)$ одни и те же общие делители. Тогда совпадают и наибольшие из них, то есть $k=k_2$.

(⇒) Пусть $a⋮t$ и $b⋮t$: $a=t\cdot x$, $b=t\cdot y$. Тогда $b-a=t(y-x)$, то есть $(b-a)⋮t$. Значит, $t$ — общий делитель $a$ и $b-a$.

(⇐) Пусть $a⋮t$ и $(b-a)⋮t$: $a=t\cdot x$, $b-a=t\cdot z$. Тогда $b=(b-a)+a=t(z+x)$, то есть $b⋮t$. Значит, $t$ — общий делитель $a$ и $b$.

Множества общих делителей равны, их максимумы равны: $\text{НОД}(a,b)=\text{НОД}(a,b-a)$. ∎

Остальные свойства:

• $\text{НОД}(a,b)=\text{НОД}(b,a)$ — в определении $a$ и $b$ входят симметрично.
• $\text{НОД}(a,1)=1$ — у единицы единственный делитель 1.
• $\text{НОД}(a,0)=a$ при $a>0$ — на $a$ делится и $a$, и 0 ($0=a\cdot 0$), а больше $a$ делителя у $a$ быть не может.

Пример

Каждый раз из большего числа вычитаем меньшее:

$$\begin{array}{rl}\text{НОД}(124,24)& =\text{НОД}(100,24)=\text{НОД}(76,24)=\text{НОД}(52,24)=\text{НОД}(28,24)\\ & =\text{НОД}(4,24)=\text{НОД}(4,20)=\text{НОД}(4,16)=\text{НОД}(4,12)\\ & =\text{НОД}(4,8)=\text{НОД}(4,4)=\text{НОД}(0,4)=4\end{array}$$

Алгоритм

$\text{НОД}(a,b)$, $a,b\in \mathbb{N}$:

пока a ≠ 0 и b ≠ 0
    если a > b
        a = a - b
    иначе
        b = b - a
вывести(a + b)

Асимптотика: $T(a,b)=O(a+b)=O(\max (a,b))$.

Не из лекции: почему ответ — $a+b$

Цикл заканчивается, когда одно из чисел стало нулём. Если $a=0$, то $a+b=b=\text{НОД}(0,b)$; если $b=0$ — симметрично. Сумма — просто способ вывести ненулевое число без ещё одного если.

Каждый шаг заменяет пару на пару с тем же НОД — это свойства выше. Значит, в конце выводится НОД исходной пары.

Не из лекции: почему остановится и почему $O(\max (a,b))$

Пока оба числа положительны, каждый шаг уменьшает $a+b$ хотя бы на 1: вычитаемое не меньше 1. Натуральная сумма не может уменьшаться бесконечно, поэтому шагов не больше $a+b$ — это $O(a+b)$.

Далее $\max (a,b)\le a+b\le 2\max (a,b)$: оценки $O(a+b)$ и $O(\max (a,b))$ отличаются константой 2 и совпадают.

Оценка достигается: $\text{НОД}(N,1)$ вычитанием делает $N-1$ шагов.

4. Алгоритм Евклида: остаток

Тот же пример, раскрашенный на лекции. Первая полоса — пока вычитаем 24:

$$\text{НОД}(124,24)\to \cdots \to \text{НОД}(4,24),4=124\%24$$

Вторая — пока вычитаем 4:

$$\text{НОД}(4,24)\to \cdots \to \text{НОД}(0,4),24\%4=0$$

Серия вычитаний одного и того же числа — это взятие остатка (Целочисленное деление и остаток).

Вывод: $\text{НОД}(a,b)=\text{НОД}(a,b\%a)$ при $b\ge a$ — работает быстрее.

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

$b\%a=b-q\cdot a$, где $q$ — неполное частное. Применим свойство $\text{НОД}(a,b)=\text{НОД}(a,b-a)$ ровно $q$ раз: $\text{НОД}(a,b)=\text{НОД}(a,b-a)=\cdots =\text{НОД}(a,b-qa)$. ∎

Алгоритм

пока a ≠ 0 и b ≠ 0
    если a > b
        a = a % b
    иначе
        b = b % a
вывести(a + b)

На том же примере — два шага вместо одиннадцати: $(124,24)\to (4,24)\to (4,0)$.

Асимптотика: $T(a,b)=O(\log (\max (a+b)))$ — на лекции без доказательства.

Не из лекции: запись оценки

На доске написано $\log (\max (a+b))$ — видимо, имелось в виду $\log (\max (a,b))$. Асимптотически это одно и то же: $\log \max (a,b)\le \log (a+b)\le \log (2\max (a,b))=1+{\log }_2\max (a,b)$.

Не из лекции: доказательство $O(\log \max (a,b))$

Лемма. Если $b\ge a>0$, то $b\%a<b/2$.

• Если $a\le b/2$: остаток меньше делителя, $b\%a<a\le b/2$.
• Если $a>b/2$: тогда $b<2a$, частное равно 1, и $b\%a=b-a<b-b/2=b/2$.

Следствие. На каждом шаге алгоритм заменяет большее число остатком — то есть уменьшает его больше чем вдвое. Посмотрим на два шага подряд. На первом меняется большее число, на втором — другое, которое к этому моменту стало большим. За два шага каждое число уменьшилось хотя бы вдвое, значит, и $\max (a,b)$ уменьшился хотя бы вдвое.

Максимум — натуральное число. Уменьшаться вдвое от $\max (a,b)$ до 0 оно может не больше ${\log }_2\max (a,b)+1$ раз, а шагов — вдвое больше: $T(a,b)\le 2{\log }_2\max (a,b)+2=O(\log \max (a,b)).$

5. Поиск key в массиве

Массив — ряд элементов, пронумерованных с нуля:

        0   1   2   3  ...
arr = [ 1 | 2 | 17| 31| ... ]
                    └── arr[3] = 31

Задача: нужно проверить, что key есть в массиве.

Алгоритм

flag = false
for i = 0 ... N
    если arr[i] = key
        flag = true
        вывести(i)
        break
если flag = false
    вывести("не нашёл")

Асимптотика: $T(N)=O(N)$, $M(N)=O(1)$.

Граница цикла

Индексы массива из N элементов — от 0 до $N-1$. На досках курса 0 ... N над массивом обычно означает полуинтервал $[0,N)$ — так записаны сортировки в L03. При таком чтении цикл выше за массив не выходит.

Но запись непостоянна: 1 ... p в L01 и 2 ... N в решете (L03) правую границу включают. Если 0 ... N включает N, последняя итерация обращается к arr[N] — за пределы массива, в C++ это Неопределённое поведение. В коде на C++ пишут явно: i < n.

Не из лекции: почему $O(N)$ и почему break не помогает

Если key в массиве нет, break не срабатывает, и цикл проверяет все N элементов. Быстрее нельзя, пока про массив ничего не известно: любой непроверенный элемент мог оказаться искомым. Оценка $O(N)$ — худший случай, тот же довод, что с break в проверке на простоту в L01.

6. Бинарный поиск

Задача: проверить, что key есть в массиве, но массив отсортирован: $a[0]\le a[1]\le \cdots \le a[N-1]$.

Идея

Берём середину M отрезка $[L,R]$ и сравниваем arr[M] с key:

• $key<arr[M]$ ⇒ ищем в левой половине;
• $key>arr[M]$ ⇒ ищем в правой половине.

За одно сравнение отбрасываем половину массива.

Алгоритм

arr = [ ... ]
L = 0
R = N - 1
пока (R - L > 1) {
    M = (L + R) / 2          // в C++: M = L + (R - L) / 2
    если arr[M] > key
        R = M
    иначе если arr[M] < key
        L = M
    иначе
        L = M
        break
}
если arr[L] = key или arr[R] = key
    вывести("нашли")
иначе
    вывести("не нашли")

Цикл идёт, пока между L и R есть хотя бы один элемент (R − L > 1). В конце остаются два соседних кандидата, их и проверяют.

Не из лекции: почему в C++ $M=L+(R-L)/2$

При больших индексах сумма L + R может не поместиться в int: например, $2000000000+2100000000=4,1\cdot 10^9$ при максимуме int $2147483647$. Переполнение знакового целого — это Неопределённое поведение. R − L не переполняется: $0\le R-L\le R$.

Значение от этого не меняется. Для $L,R\ge 0$ и $d=R-L$: $\lfloor (L+R)/2\rfloor =\lfloor (2L+d)/2\rfloor =L+\lfloor d/2\rfloor$.

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

Инвариант: если key есть в массиве, то он лежит среди $arr[L],\dots ,arr[R]$.

• Вначале $L=0$, $R=N-1$ — это весь массив.
• arr[M] > key: массив отсортирован, поэтому при $i\ge M$ $arr[i]\ge arr[M]>key$, и справа от $M$ искомого нет. Он в $[L,M-1]\subset [L,M]$ — после R = M инвариант сохранён.
• arr[M] < key: симметрично, искомое в $[M+1,R]\subset [M,R]$.
• arr[M] = key: найден, L = M, break — финальная проверка arr[L] = key его увидит.

Остановка. При $R-L>1$ середина лежит строго внутри: $L<M<R$. Значит, R = M или L = M строго уменьшает $R-L$, и цикл закончится.

Ответ. После цикла $R-L\le 1$: в отрезке не больше двух элементов, L и R. По инварианту, если key есть, он среди них — проверка обоих даёт верный ответ.

Крайний случай: при $N=0$ получится $R=-1$, и проверка arr[L] обратится к несуществующему элементу. Пустой массив надо проверять до поиска.

Асимптотика

Сколько элементов остаётся после каждого шага:

шаг 0  →  N
шаг 1  →  N/2
шаг 2  →  N/4
шаг 3  →  N/8
 ...
шаг k  →  N/2^k
итого  ?  шагов  →  1

$$1=\frac{N}{2^k}\Rightarrow 2^k=N\Rightarrow k={\log }_{2}N,T(N)=O(\log N)$$

Не из лекции: то же аккуратно

Пусть $d=R-L$. Середина делит отрезок на части $M-L=\lfloor d/2\rfloor$ и $R-M=\lceil d/2\rceil$, и остаётся одна из них. Значит, новое $d\le \lceil d/2\rceil$. Начиная с $d=N-1$, после $k$ шагов $d\le \lceil (N-1)/2^k\rceil$. Цикл заканчивается, когда $d\le 1$, — не позже чем через $\lceil {\log }_{2}N\rceil$ шагов. Каждый шаг — несколько тактов, память — только L, R, M: $T(N)=O(\log N)$, $M(N)=O(1)$.

Сравнение

N	Оценка	Итераций	Время при $10^8$ итер./с
$10^{12}$	$T(N)=O(N)$	$\sim 10^{12}$	$\sim 10^4$ с
$10^{12}$	$T(N)=O(\log N)$	$\log 10^{12}\approx 40$	$\sim 40/10^8$ с

$10^4$ секунд — почти три часа. Здесь логарифм двоичный: ${\log }_{2}10^{12}\approx 39,9$.

7. Бинарный поиск по ответу

Различие:

• обычный — ищем число в массиве;
• по ответу — ищем число, но в функции.

Если функция $f(x)$ монотонная на $[L,R]$, её значения упорядочены так же, как элементы отсортированного массива: $arr[x]\leftrightarrow f(x)$. Значит, тем же делением пополам можно искать $x$, при котором $f(x)$ равна нужному значению. Подробнее — Бинарный поиск.

Дробные числа: корень

Задача: найти $\sqrt{N}=M$. По определению $M^2=N$ — ищем $M$, при котором монотонная функция $f(M)=M^2$ равна N.

Вариант 1 — до точности eps:

float L = 0, R = N           // почему √N ∈ [0; N]
eps = 10^-5
пока (|L*L - N| > eps) {
    M = (L + R) / 2
    если M*M < N
        L = M
    иначе
        R = M
}

Вариант 2 — фиксированное число итераций (на полях: «гарантия количества итераций»):

float L = 0, R = N
for i = 0 ... 1000
    M = (L + R) / 2
    если M*M < N
        L = M
    иначе
        R = M

Не из лекции: почему $\sqrt{N}\in [0;N]$

Корень неотрицателен. При $N\ge 1$: $N\le N^2$, извлекаем корень — $\sqrt{N}\le N$. При $0<N<1$ это неверно: $\sqrt{0,25}=0,5>0,25$. Для таких N правую границу берут $R=1$, в общем случае $R=\max (1,N)$.

Не из лекции: почему это работает

Инвариант: $L^2<N\le R^2$, то есть $\sqrt{N}\in [L,R]$. Вначале $0<N$ и $N\le N^2$ (при $N\ge 1$). Ветка M*M < N сохраняет левую половину неравенства, ветка «иначе» — правую. Отрезок каждый раз уменьшается вдвое: после $k$ итераций $R-L=N/2^k$.

Не из лекции: почему вариант 1 может зависнуть — проверено

float хранит около 7 значащих цифр. Рядом с числом 100 соседние значения float отстоят примерно на $10^{-5}$, рядом с $10^6$ — на $0,06$. Когда отрезок сжимается до соседних чисел, L перестаёт меняться, а $L^2$ так и не попадает в $N\pm 10^{-5}$. Точность $10^{-5}$ просто недостижима.

Прогон варианта 1 на float, ограниченный $10^7$ итерациями (GCC 16, -O0):

N	Вариант 1 (eps)	Вариант 2: полезных итераций из 1000
2	стоп за 19 итераций	24
10	стоп за 22 итерации	26
100	завис	26
$10^6$	завис	34

Вариант 2 останавливается всегда. После 24–34 итераций L и R уже соседние float, и оставшиеся итерации ничего не меняют. Это та же мысль, что в Типы с плавающей точкой: допуск должен соответствовать масштабу чисел.

Грабли

• Бинарный поиск по неотсортированному массиву даёт неверный ответ без всякой ошибки: отбрасывание половины опирается на порядок.
• M = (L + R) / 2 в C++ может переполнить int — пишут L + (R − L) / 2.
• for i = 0 ... N на доске обычно значит $[0,N)$; если граница включается, последняя итерация уходит за массив. В C++ — явное i < n.
• Цикл по eps на дробных числах может не остановиться. Фиксированное число итераций гарантирует остановку.
• $\sqrt{N}\in [0;N]$ только при $N\ge 1$.
• Евклид вычитанием на паре $(N,1)$ делает $N-1$ шагов. С остатком — один.

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

• разложить число на простые множители и объяснить, почему алгоритм выводит только простые;
• доказать $\text{НОД}(a,b)=\text{НОД}(a,b-a)$ и $\text{НОД}(a,b)=\text{НОД}(a,b\%a)$;
• объяснить, почему Евклид с остатком работает за $O(\log \max (a,b))$;
• написать бинарный поиск и доказать его правильность через инвариант;
• вывести $O(\log N)$ из «каждый шаг — вдвое меньше»;
• объяснить, зачем в C++ L + (R − L) / 2;
• найти корень бинарным поиском по ответу и объяснить, почему цикл по eps опасен.