АиСД L01 - Время работы и асимптотика

О чём лекция

Как сравнивать алгоритмы, если один и тот же код на разных компьютерах работает от сотых долей секунды до минут. Время измеряется в тактах, а важен не точный счёт, а то, как он растёт с длиной входа. Для этого вводятся оценки O, Ω и Θ — язык, на котором дальше в курсе будет описан любой алгоритм. В конце — три версии проверки числа на простоту и их оценки.

Маршрут

1. Что измеряем → Время работы алгоритма
2. Как описываем рост → Асимптотические оценки
3. Сколько стоит цикл → Циклы

1. Алгоритмы и структуры данных

Структуры данных нужны, чтобы хранить информацию.

Что оптимизируем в алгоритме:

• время работы (time) — обозначается T;
• память (memory) — обозначается M.

На полях рядом перечислены ещё «улучшить визуал», «многопоточность», «безопасность» — без пояснений. По-видимому, это другие стороны оптимизации; на лекции дальше разбирались только время и память.

2. Время работы

Один и тот же алгоритм выполняет $10^9$ тактов. Запустим его на трёх компьютерах:

Компьютер	Скорость	Время работы
мой	$10^8$ тактов/с	10 с
бабушкин	$10^7$ тактов/с	100 с
МФТИ	$10^{11}$ тактов/с	0,01 с

Секунды зависят от компьютера, а число тактов — нет. Поэтому время переводится в такты.

Модель, в которой так считают, — RAM-модель. Такт — простейшее действие:

• сравнение;
• присвоение;
• создание переменной.

Подробнее — Время работы алгоритма.

3. Память

N — длина входа   ──вход──▶  [ Алгоритм ]  ──выход──▶
                               компьютер
                           memory: доп. память

N — длина входа. Кроме памяти под вход и выход алгоритму может понадобиться дополнительная память — её и оценивают.

4. Зависимость тактов от длины входа

На графике по горизонтали — длина входа N (отмечены 10 и 100), по вертикали — такты, то есть время.

• Экспериментальный график — ломаная по замерам: растёт, но с колебаниями, местами даже проседает.
• «Моё предположение — тенденция» — плавная кривая, проведённая сквозь замеры.

Интересна именно тенденция: как растёт число тактов при росте N. Её и описывают оценки.

5. Оценки: O, Ω, Θ

Пусть $g(n)$ — число тактов (наши данные), $f(n)$ — функция, с которой сравниваем.

O — «О-большое»

$g(n)=O(f(n))$ — «наши данные оценены сверху функцией $f$».

$$g(n)=O(f(n))⟺\exists c>0\exists N\in \mathbb{N}\forall n>N:g(n)\le c\cdot f(n)$$

На графике: до точки N кривая $g(n)$ может подниматься выше $c\cdot f(n)$, а после N всегда остаётся под ней.

Ω — «омега»

$$g(n)=\Omega (f(n))⟺\exists c>0\exists N\in \mathbb{N}\forall n>N:g(n)\ge c\cdot f(n)$$

Зеркально: после точки N кривая $g(n)$ всегда выше $c\cdot f(n)$ — оценка снизу.

Θ — «тета»

$$g(n)=\Theta (f(n))⟺\exists c_1,c_2>0\exists N\in \mathbb{N}\forall n>N:c_{1}f(n)\le g(n)\le c_{2}f(n)$$

После точки N кривая $g(n)$ зажата между $c_{1}f(n)$ и $c_{2}f(n)$ — оценка с обеих сторон.

Подробнее — Асимптотические оценки.

6. Асимптотика

От медленного роста к быстрому:

Оценка	Название
$O(1)$	константа: $g(n)\le c\cdot 1=c$
$O(\log N)$	логарифм
$O(\sqrt{N})$	корневая
$O(N)$	линейная
$O(N\log N)$
$O(N^2)$
…
$O(N!)$

На лекции сказали, что основание логарифма может быть любым.

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

Логарифмы по разным основаниям отличаются только постоянным множителем:

${\log }_{a}N=\frac{{\log }_{b}N}{{\log }_{b}a}$

Например, ${\log }_{2}N={\log }_{10}N/{\log }_{10}2\approx 3,3\cdot {\log }_{10}N$ при любом N. А постоянный множитель в O-оценке поглощается константой $c$ из определения: если $g(n)\le c\cdot {\log }_{2}n$, то $g(n)\le (3,3c)\cdot {\log }_{10}n$. Поэтому $O({\log }_{2}N)$, $O({\log }_{10}N)$ и $O(\ln N)$ — одна и та же оценка, и основание не пишут.

Таблица сравнения

$N=10^8$, компьютер делает $10^8$ тактов в секунду:

Время работы	Тактов	Секунд
$T(N)=O(N)$	$\sim 10^8$	1
$T(N)=O(\sqrt{N})$	$\sim 10^4$	$1/10^4$
$T(N)=O(\log N)$	$\sim 18$	$18/10^8$
$T(N)=O(N^2)$	$\sim 10^{16}$	$10^8$

$10^8$ секунд — больше трёх лет. Разница между линейным и квадратичным алгоритмом на таком входе — секунда против нескольких лет.

Не из лекции: откуда 18

18 — это натуральный логарифм: $\ln 10^8\approx 18,4$. Двоичный дал бы ${\log }_{2}10^8\approx 26,6$. На вывод таблицы это не влияет: в обоих случаях это десятки тактов против $10^8$.

7. Упрощение оценок

Пример 1. $O(10\cdot N)=O(N)$.

Если $f(n)\le c_1\cdot 10\cdot n$, то $f(n)\le (10\cdot c_1)\cdot n$. Обозначим $c_2=10\cdot c_1$ — получили $f(n)\le c_2\cdot n$, то есть $O(N)$. Постоянный множитель уходит в константу.

Пример 2. $O(N^2+N)=O(N^2)$.

Из $f(n)\le c_1(N^2+N)$ получаем $f(n)\le c_2\cdot N^2$ с $c_2=10\cdot c_1$.

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

При $N\ge 1$ выполнено $N\le N^2$, значит $N^2+N\le 2N^2$ и $c_1(N^2+N)\le 2c_1\cdot N^2$. Достаточно было бы $c_2=2c_1$; $10c_1$ из лекции тоже подходит, просто с запасом. Младшее слагаемое поглощается старшим.

8. Проверка числа на простоту

$p\in \mathbb{N}$ простое, если у него 2 делителя — $p$ и 1.

Запись $p⋮i$ — «$p$ делится на $i$».

Вариант а — перебрать все делители

counter = 0
for i = 1 ... p
    если p ⋮ i
        counter += 1
если counter = 2
    число простое
иначе
    не простое

Подсчёт тактов:

• counter = 0 — 1 такт;
• тело цикла — не больше 2 тактов, и выполняется оно N раз;
• проверка counter = 2 в конце — 2 такта.

$$\Sigma =2+1+2\cdot N=3+2N\text{ тактов},T(N)=O(3+2N)=O(N)\text{ — линейная.}$$

Как считается стоимость цикла — Циклы.

Вариант б — до первого делителя

counter = 0
for i = 2 ... p-1
    если p ⋮ i
        counter += 1
        break
если counter = 0
    число простое
иначе
    не простое

Проверяем только «лишние» делители — от 2 до $p-1$ — и останавливаемся на первом найденном. $T(N)=O(N)$.

Не из лекции: почему break не улучшил оценку

Если $p$ простое, делителя в диапазоне нет, break не срабатывает, и цикл проходит все $p-2$ итерации. Оценка O описывает рост сверху, поэтому определяет её именно такой, самый долгий случай.

Вариант в — до корня

counter = 0
for i = 2 ... ⌈√N + 1⌉
    если p ⋮ i
        counter += 1
        break
если counter = 0
    число простое
иначе
    не простое

$T(N)=O(\sqrt{N})$.

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

Если $p=a\cdot b$ и оба множителя больше $\sqrt{p}$, то $a\cdot b>\sqrt{p}\cdot \sqrt{p}=p$ — противоречие. Значит, у составного числа есть делитель не больше $\sqrt{p}$, и дальше искать незачем.

Обозначения в этом разделе

В разделе 3 N — длина входа. Здесь $T(N)$ считается по самому числу $p$: цикл варианта «а» делает $p$ итераций. В варианте «в» граница записана как $\sqrt{N}$ — по смыслу это $\sqrt{p}$. Конспект повторяет запись лекции.

Не из лекции: число 1

Для $p=1$ в вариантах «б» и «в» цикл не выполняется ни разу, counter остаётся 0, и ответ — «простое». По определению выше у 1 один делитель, и она не простая. Вариант «а» отвечает верно: counter = 1. Чтобы «б» и «в» были правильными, 1 нужно проверять отдельно.

Грабли

• Сравнивать алгоритмы в секундах. Тот же алгоритм на другом компьютере работает в 10 раз дольше или в 1000 раз быстрее. Сравнивают такты и их рост.
• Путать O, Ω и Θ. O — оценка сверху, Ω — снизу, Θ — с обеих сторон сразу.
• Выписывать константы и основания. $O(10N)$, $O(N^2+N)$ и $O({\log }_{2}N)$ пишутся как $O(N)$, $O(N^2)$ и $O(\log N)$.
• Верить, что break всегда ускоряет. В худшем случае он не срабатывает, и оценка остаётся прежней.
• Забыть про $p=1$ в проверке на простоту.

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

• объяснить, почему время работы меряют в тактах, а не в секундах;
• записать определения O, Ω и Θ и нарисовать к каждому картинку;
• упорядочить $O(N^2)$, $O(\log N)$, $O(N)$, $O(1)$, $O(N!)$, $O(\sqrt{N})$, $O(N\log N)$ по скорости роста;
• прикинуть по таблице, уложится ли алгоритм в секунду при $N=10^8$;
• посчитать такты простого цикла и свести результат к O-оценке;
• объяснить, почему проверка на простоту до $\sqrt{p}$ правильна и почему она быстрее.