{ "cells": [ { "cell_type": "markdown", "id": "intro", "metadata": {}, "source": [ "# Лекция 2. Модель RAM и асимптотики алгоритмов\n", "\n", "## План\n", "\n", "1. Модель RAM, нотации $O$, $\\Omega$, $\\Theta$. Чем `list` в Python отличается от массива модели.\n", "2. Полный перебор на примере делителей числа. Почему достаточно идти до $\\sqrt{x}$.\n", "3. Методы недели: частоты, два указателя, окно, префиксные суммы и разностный массив.\n", "\n", "На лекции 1 мы ввели алгоритм как ~вычислимую функцию~ *последовательность команд на формальном языке исполнителя, **приводящую к цели** за конечное время*.\n", "Если для записи алгоритма мы используем *язык программирования*, то есть и исполнитель формальных команд, который будет их выполнять детерминированно.\n", "Однако, чтобы программа действительно была алгоритмом, она должна быть **корректной** и не зацикливаться.\n", "\n", "Сегодня разбираем второй критерий: **эффективность** — как время и память зависят от размера входа. Это невозможно обсуждать пока нет модели самого исполнителя." ] }, { "cell_type": "markdown", "id": "ram", "metadata": {}, "source": [ "## Модель RAM\n", "\n", "**RAM** (random-access machine) — учебная машина, в которой память выглядит как массив ячеек. У каждой ячейки есть номер (индекс). Прочитать значение или записать новое по известному индексу — **элементарная операция**: в модели она стоит $O(1)$, независимо от того, первая это ячейка или миллионная.\n", "\n", "Кроме доступа к памяти к элементарным относят арифметику и сравнение **машинного слова** (фиксированное число бит) и переход к другой команде.\n", "\n", "Время работы и дополнительная память — функции от **размера входа** $n$: длины массива, числа запросов. Мы сравниваем, как эти функции растут, когда $n$ становится большим, а не сколько миллисекунд занял один прогон на ноутбуке.\n", "\n", "**Оговорка про Python.** Объект `int` может занимать сколько угодно цифр. Сложение двух тысячезначных чисел уже не $O(1)$. На типичных ограничениях задач ($\\lvert a_i\\rvert \\le 10^9$) арифметику считаем элементарной. Если когда-нибудь вход — «число из $10^5$ цифр», модель нужно поправить.\n" ] }, { "cell_type": "markdown", "id": "notations", "metadata": {}, "source": [ "## Нотации $O$, $\\Omega$, $\\Theta$\n", "\n", "Пусть $T(n)$ — число элементарных операций в худшем случае на входе размера $n$.\n", "\n", "- $T(n) = O(f(n))$ — существует константа $c > 0$, такая что для больших $n$ верно $T(n) \\le c\\cdot f(n)$. Верхняя оценка: «не хуже, чем порядка $f$».\n", "- $T(n) = \\Omega(f(n))$ — нижняя оценка: «не лучше, чем порядка $f$».\n", "- $T(n) = \\Theta(f(n))$ — обе сразу: рост как у $f$.\n", "\n", "Примеры, которые понадобятся на этой неделе:\n", "\n", "- один цикл `for i in range(n)` без вложенного — $\\Theta(n)$;\n", "- два вложенных цикла по $n$ — $\\Theta(n^2)$;\n", "- $\\log n$ растёт медленнее любого положительного полинома; $2^n$ — быстрее.\n", "\n", "Пока не сказано иное, оцениваем **наихудший** случай. Лучший и средний упоминаем, когда алгоритм на «удачном» входе ведёт себя заметно иначе.\n", "\n", "`list.append` в конец обычно дешёвый: время от времени список переезжает в больший кусок памяти, но в среднем на одну вставку это $O(1)$ (амортизация). Подробный разбор — не сегодня.\n" ] }, { "cell_type": "markdown", "id": "pylist", "metadata": {}, "source": [ "## `list` — не массив\n", "\n", "В модели ячейка хранит слово. В Python выражение `a = [3, 1, 4]` строит **динамический массив ссылок**. Внутри лежат указатели на три отдельных объекта `int`, а не три подряд идущие машинные ячейки с тройкой, единицей и четвёркой.\n", "\n", "Следствия:\n", "\n", "- `a[i]` по-прежнему $O(1)$: до указателя доходим за константу. Константа больше, чем у массива `int` в C.\n", "- Память больше: каждый объект несёт заголовок, список держит запас свободных слотов.\n", "- Длина меняется. Это удобно, но это уже не «выделили ровно $n$ ячеек и живём».\n", "\n", "Когда на семинаре говорят «заведите массив из $1001$ счётчика», имеют в виду `list` длины $1001$. Модель RAM к нему применима по индексу; по константам и картинке памяти — нет.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "list-index", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "10 30\n", "[10, 99, 30]\n" ] } ], "source": [ "a = [10, 20, 30]\n", "print(a[0], a[2])\n", "a[1] = 99\n", "print(a)" ] }, { "cell_type": "markdown", "id": "divisors", "metadata": {}, "source": [ "## Делители и полный перебор\n", "\n", "Задача: по натуральному $x$ выписать все его положительные делители. Для $x = 12$ это $1, 2, 3, 4, 6, 12$.\n", "\n", "Наивный способ — проверить каждый кандидат $a = 1, 2, \\ldots, x$: делит или нет. Кандидатов ровно $x$.\n", "\n", "Такой подход называют **полным перебором**: перебрали всё пространство возможных ответов-делителей.\n", "\n", "На $x = 12$ это мгновенно. На $x$ порядка $10^9$ цикл из миллиарда шагов уже нереалистичен.\n", "\n", "Важно: здесь время растёт как **величина** числа $x$, а не как длина его записи (у $10^9$ всего 10 цифр). Это другой «размер входа», чем длина массива в блоке 1.\n", "\n", "Полный перебор — ярлык для «проверили всех». Это не отдельная линия семестра. Дальше мы как раз учимся его не делать там, где есть структура.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "div-naive", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 2 3 4 6 12\n" ] } ], "source": [ "# полный перебор делителей для маленького x\n", "x = 12\n", "for a in range(1, x + 1):\n", " if x % a == 0:\n", " print(a, end=' ')\n", "print()\n" ] }, { "cell_type": "markdown", "id": "sqrt", "metadata": {}, "source": [ "## Парность делителей и $\\sqrt{x}$\n", "\n", "Если $x = a\\cdot b$ и оба множителя натуральные, делители ходят **парами**: $a$ и $b = x/a$.\n", "\n", "Хотя бы один из пары не больше $\\sqrt{x}$. Иначе $a > \\sqrt{x}$ и $b > \\sqrt{x}$, откуда $a\\cdot b > x$. Значит, достаточно перебрать $a$ от $1$ до $\\lfloor\\sqrt{x}\\rfloor$: если $a$ делит $x$, в ответ идут и $a$, и $x/a$ (если они различны).\n", "\n", "Та же граница работает для проверки «$x$ простое»: нашёлся делитель строго между $1$ и $x$ — составное; иначе простое (для $x > 1$).\n", "\n", "Число шагов тогда порядка $\\sqrt{x}$, а не $x$. Для $x = 12$ достаточно смотреть $a = 1,2,3$.\n", "\n", "Дальше в теорию чисел на этой лекции не идём.\n" ] }, { "cell_type": "markdown", "id": "linear", "metadata": {}, "source": [ "## Линейный проход\n", "\n", "Простейший приём на массиве: один раз идти слева направо и обновлять несколько переменных (сумма, максимум, ответ). Это $\\Theta(n)$ времени и, если не копировать вход ещё раз, мало дополнительной памяти.\n", "\n", "На семинаре 1 вход часто был потоком и в список не складывался. Здесь массив уже дан: проход тот же, но можно возвращаться по индексу.\n" ] }, { "cell_type": "markdown", "id": "freq", "metadata": {}, "source": [ "## Частотный массив\n", "\n", "Индекс не обязан значить «позиция во входе». Если значения лежат в **известном малом диапазоне** (например, от $0$ до $1000$), можно завести массив, у которого индекс — само значение, а в ячейке — сколько раз оно встретилось или иной итог.\n", "\n", "Один проход по входу заполняет сводку. Кто ни разу не встретился, у того в сводке ноль — это не то же самое, что «значение $0$».\n", "\n", "Так готовят почву к сортировке подсчётом: сначала сводка по ключам, потом можно восстановить порядок.\n" ] }, { "cell_type": "markdown", "id": "twopointers", "metadata": {}, "source": [ "## Два указателя\n", "\n", "Идея: не смотреть все пары индексов ($\\Theta(n^2)$), а двигать две позиции так, чтобы инвариант сохранялся.\n", "\n", "Три типичные картинки (без готового кода задач):\n", "\n", "- **Две головы.** Два уже упорядоченных массива. В каждый момент достаточно сравнить текущие начала: кого-то забираем, указатель только вперёд.\n", "- **Два конца.** Один упорядоченный массив. Сумма концов слишком большая или слишком маленькая подсказывает, какой край сузить.\n", "- **На месте.** Часть элементов должна остаться якорями, часть — переставиться. Второй массив не обязателен, если хватает двух позиций в том же списке.\n", "\n", "На больших $n$ вложенный перебор пар не успеет. Указатели — способ оставить линейное (или почти линейное) число шагов.\n" ] }, { "cell_type": "markdown", "id": "window", "metadata": {}, "source": [ "## Скользящее окно\n", "\n", "Нужен итог (часто сумма) на каждом отрезке фиксированной длины $k$: сначала индексы $1\\ldots k$, затем $2\\ldots k+1$, и так далее.\n", "\n", "Соседние окна **почти совпадают**: из левого края один элемент вышел, справа один вошёл. Значит, итог следующего окна получается из предыдущего, а не складыванием $k$ чисел заново.\n", "\n", "Если каждый раз суммировать окно с нуля, получится порядка $n\\cdot k$ сложений. При больших $n$ и $k$ это тот же класс, что квадрат.\n" ] }, { "cell_type": "markdown", "id": "prefix", "metadata": {}, "source": [ "## Префиксные суммы и разностный массив\n", "\n", "**Префикс.** Пусть $p_k$ — сумма первых $k$ элементов ($p_0 = 0$). Сумма на отрезке с индексами от $l$ до $r$ включительно выражается через две заготовки $p$, без повторного прохода по отрезку. Предподсчёт — один линейный проход; дальше каждый запрос дешёвый.\n", "\n", "Пример на четырёх числах. Массив $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$.\n", "\n", "Частая ошибка — спутать включение правого конца с полуинтервалом.\n", "\n", "**Разность.** Обратная операция: много раз «прибавить число на отрезке», потом один раз восстановить массив. Вместо того чтобы на каждое прибавление бежать по всем ячейкам отрезка, оставляют следы на границах и делают один проход в конце. Это снова $\\Theta(n + q)$, а не $\\Theta(nq)$.\n" ] }, { "cell_type": "markdown", "id": "prefix2d", "metadata": {}, "source": [ "## Двумерные префиксы (если осталось время)\n", "\n", "На прямоугольной таблице можно заранее посчитать сумму в каждом префиксном прямоугольнике от левого верхнего угла. Сумма произвольного прямоугольника с углами $(x_1, y_1)$ и $(x_2, y_2)$ (включительно) собирается из **четырёх** таких заготовок: большой угол минус два «лишних» прямоугольника плюс угол, который вычли дважды.\n", "\n", "На семинаре 2 этой задачи нет. Достаточно картинки включения-исключения.\n" ] }, { "cell_type": "markdown", "id": "seminar", "metadata": {}, "source": [ "## К семинару 2\n", "\n", "На паре — те же идеи в задачах: частоты, слияние, пара с заданной суммой, суммы на отрезках, окно, перестановка на месте, диапазонные прибавления, медиана по счётчикам. Две последние — запас.\n", "\n", "Тестер ограничивает время примерно двумя секундами на тест. Решение, которое перебирает все пары или заново складывает каждый отрезок, на больших входах получит TLE: это не «другой ответ», а «слишком медленно».\n", "\n", "В этом конспекте нет готовых решений задач семинара. Их собираете вы.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.13" } }, "nbformat": 4, "nbformat_minor": 5 }