Лекция 2. Модель RAM и асимптотики алгоритмов

План

1. Модель RAM, нотации $O$, $\Omega$, $\Theta$. Чем list в Python отличается от массива модели.
2. Полный перебор на примере делителей числа. Почему достаточно идти до $\sqrt{x}$.
3. Методы недели: частоты, два указателя, окно, префиксные суммы и разностный массив.

На лекции 1 мы ввели алгоритм как ~вычислимую функцию~ последовательность команд на формальном языке исполнителя, приводящую к цели за конечное время. Если для записи алгоритма мы используем язык программирования, то есть и исполнитель формальных команд, который будет их выполнять детерминированно. Однако, чтобы программа действительно была алгоритмом, она должна быть корректной и не зацикливаться.

Сегодня разбираем второй критерий: эффективность — как время и память зависят от размера входа. Это невозможно обсуждать пока нет модели самого исполнителя.

Модель RAM

RAM (random-access machine) — учебная машина, в которой память выглядит как массив ячеек. У каждой ячейки есть номер (индекс). Прочитать значение или записать новое по известному индексу — элементарная операция: в модели она стоит $O(1)$, независимо от того, первая это ячейка или миллионная.

Кроме доступа к памяти к элементарным относят арифметику и сравнение машинного слова (фиксированное число бит) и переход к другой команде.

Время работы и дополнительная память — функции от размера входа $n$: длины массива, числа запросов. Мы сравниваем, как эти функции растут, когда $n$ становится большим, а не сколько миллисекунд занял один прогон на ноутбуке.

Оговорка про Python. Объект int может занимать сколько угодно цифр. Сложение двух тысячезначных чисел уже не $O(1)$. На типичных ограничениях задач ($\lvert a_i\rvert \le 10^9$) арифметику считаем элементарной. Если когда-нибудь вход — «число из $10^5$ цифр», модель нужно поправить.

Нотации $O$, $\Omega$, $\Theta$

Пусть $T(n)$ — число элементарных операций в худшем случае на входе размера $n$.

• $T(n) = O(f(n))$ — существует константа $c > 0$, такая что для больших $n$ верно $T(n) \le c\cdot f(n)$. Верхняя оценка: «не хуже, чем порядка $f$».
• $T(n) = \Omega(f(n))$ — нижняя оценка: «не лучше, чем порядка $f$».
• $T(n) = \Theta(f(n))$ — обе сразу: рост как у $f$.

Примеры, которые понадобятся на этой неделе:

• один цикл for i in range(n) без вложенного — $\Theta(n)$;
• два вложенных цикла по $n$ — $\Theta(n^2)$;
• $\log n$ растёт медленнее любого положительного полинома; $2^n$ — быстрее.

Пока не сказано иное, оцениваем наихудший случай. Лучший и средний упоминаем, когда алгоритм на «удачном» входе ведёт себя заметно иначе.

list.append в конец обычно дешёвый: время от времени список переезжает в больший кусок памяти, но в среднем на одну вставку это $O(1)$ (амортизация). Подробный разбор — не сегодня.

list — не массив

В модели ячейка хранит слово. В Python выражение a = [3, 1, 4] строит динамический массив ссылок. Внутри лежат указатели на три отдельных объекта int, а не три подряд идущие машинные ячейки с тройкой, единицей и четвёркой.

Следствия:

• a[i] по-прежнему $O(1)$: до указателя доходим за константу. Константа больше, чем у массива int в C.
• Память больше: каждый объект несёт заголовок, список держит запас свободных слотов.
• Длина меняется. Это удобно, но это уже не «выделили ровно $n$ ячеек и живём».

Когда на семинаре говорят «заведите массив из $1001$ счётчика», имеют в виду list длины $1001$. Модель RAM к нему применима по индексу; по константам и картинке памяти — нет.

Делители и полный перебор

Задача: по натуральному $x$ выписать все его положительные делители. Для $x = 12$ это $1, 2, 3, 4, 6, 12$.

Наивный способ — проверить каждый кандидат $a = 1, 2, \ldots, x$: делит или нет. Кандидатов ровно $x$.

Такой подход называют полным перебором: перебрали всё пространство возможных ответов-делителей.

На $x = 12$ это мгновенно. На $x$ порядка $10^9$ цикл из миллиарда шагов уже нереалистичен.

Важно: здесь время растёт как величина числа $x$, а не как длина его записи (у $10^9$ всего 10 цифр). Это другой «размер входа», чем длина массива в блоке 1.

Полный перебор — ярлык для «проверили всех». Это не отдельная линия семестра. Дальше мы как раз учимся его не делать там, где есть структура.

Парность делителей и $\sqrt{x}$

Если $x = a\cdot b$ и оба множителя натуральные, делители ходят парами: $a$ и $b = x/a$.

Хотя бы один из пары не больше $\sqrt{x}$. Иначе $a > \sqrt{x}$ и $b > \sqrt{x}$, откуда $a\cdot b > x$. Значит, достаточно перебрать $a$ от $1$ до $\lfloor\sqrt{x}\rfloor$: если $a$ делит $x$, в ответ идут и $a$, и $x/a$ (если они различны).

Та же граница работает для проверки «$x$ простое»: нашёлся делитель строго между $1$ и $x$ — составное; иначе простое (для $x > 1$).

Число шагов тогда порядка $\sqrt{x}$, а не $x$. Для $x = 12$ достаточно смотреть $a = 1,2,3$.

Дальше в теорию чисел на этой лекции не идём.

Линейный проход

Простейший приём на массиве: один раз идти слева направо и обновлять несколько переменных (сумма, максимум, ответ). Это $\Theta(n)$ времени и, если не копировать вход ещё раз, мало дополнительной памяти.

На семинаре 1 вход часто был потоком и в список не складывался. Здесь массив уже дан: проход тот же, но можно возвращаться по индексу.

Частотный массив

Индекс не обязан значить «позиция во входе». Если значения лежат в известном малом диапазоне (например, от $0$ до $1000$), можно завести массив, у которого индекс — само значение, а в ячейке — сколько раз оно встретилось или иной итог.

Один проход по входу заполняет сводку. Кто ни разу не встретился, у того в сводке ноль — это не то же самое, что «значение $0$».

Так готовят почву к сортировке подсчётом: сначала сводка по ключам, потом можно восстановить порядок.

Два указателя

Идея: не смотреть все пары индексов ($\Theta(n^2)$), а двигать две позиции так, чтобы инвариант сохранялся.

Три типичные картинки (без готового кода задач):

• Две головы. Два уже упорядоченных массива. В каждый момент достаточно сравнить текущие начала: кого-то забираем, указатель только вперёд.
• Два конца. Один упорядоченный массив. Сумма концов слишком большая или слишком маленькая подсказывает, какой край сузить.
• На месте. Часть элементов должна остаться якорями, часть — переставиться. Второй массив не обязателен, если хватает двух позиций в том же списке.

На больших $n$ вложенный перебор пар не успеет. Указатели — способ оставить линейное (или почти линейное) число шагов.

Скользящее окно

Нужен итог (часто сумма) на каждом отрезке фиксированной длины $k$: сначала индексы $1\ldots k$, затем $2\ldots k+1$, и так далее.

Соседние окна почти совпадают: из левого края один элемент вышел, справа один вошёл. Значит, итог следующего окна получается из предыдущего, а не складыванием $k$ чисел заново.

Если каждый раз суммировать окно с нуля, получится порядка $n\cdot k$ сложений. При больших $n$ и $k$ это тот же класс, что квадрат.

Префиксные суммы и разностный массив

Префикс. Пусть $p_k$ — сумма первых $k$ элементов ($p_0 = 0$). Сумма на отрезке с индексами от $l$ до $r$ включительно выражается через две заготовки $p$, без повторного прохода по отрезку. Предподсчёт — один линейный проход; дальше каждый запрос дешёвый.

Пример на четырёх числах. Массив $2, 1, 3, 1$. Префиксы: $0$; $2$; $2+1=3$; $3+3=6$; $6+1=7$. Сумма с 2-го по 4-й элемент (единицы) — это «всё до 4-го» минус «всё до 1-го»: $7-2=5$. Проверка: $1+3+1=5$.

Частая ошибка — спутать включение правого конца с полуинтервалом.

Разность. Обратная операция: много раз «прибавить число на отрезке», потом один раз восстановить массив. Вместо того чтобы на каждое прибавление бежать по всем ячейкам отрезка, оставляют следы на границах и делают один проход в конце. Это снова $\Theta(n + q)$, а не $\Theta(nq)$.

Двумерные префиксы (если осталось время)

На прямоугольной таблице можно заранее посчитать сумму в каждом префиксном прямоугольнике от левого верхнего угла. Сумма произвольного прямоугольника с углами $(x_1, y_1)$ и $(x_2, y_2)$ (включительно) собирается из четырёх таких заготовок: большой угол минус два «лишних» прямоугольника плюс угол, который вычли дважды.

На семинаре 2 этой задачи нет. Достаточно картинки включения-исключения.

К семинару 2

На паре — те же идеи в задачах: частоты, слияние, пара с заданной суммой, суммы на отрезках, окно, перестановка на месте, диапазонные прибавления, медиана по счётчикам. Две последние — запас.

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

В этом конспекте нет готовых решений задач семинара. Их собираете вы.