Конспект раздела: анализ времени и памяти

Карта раздела

Раздел отвечает на второй вопрос про алгоритм - не «верен ли», а «сколько стоит». Четыре главы выстраиваются в одну дорогу от точного счёта к оценке порядка.

счёт операций   ->  T(n) построчно: цена × число выполнений
     |
асимптотика     ->  огрубить T(n) до порядка: O, Θ, Ω
     |
суммы           ->  свернуть ряд из цикла и оценить его интегралом
     |
случаи и память ->  какой вход берём (худший/средний) и сколько памяти сверх входа

Таблица порядков роста

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

Порядок	×2 к входу даёт	Откуда берётся	Пример
`1`	столько же	работа не зависит от `n`	обращение по индексу
`log n`	+константа	деление пополам; гармонический ряд	двоичный поиск
`n`	×2	один проход; геометрический ряд	сумма списка
`n·log n`	чуть больше ×2	`n` проходов по делению пополам; `n·Hₙ`	быстрая сортировка
`n²`	×4	арифметический ряд; все пары	сортировка вставками (худший)
`n³`	×8	все тройки	перемножение матриц «в лоб»
`2ⁿ`	возводится в квадрат	все подмножества (×2 на элемент)	перебор подмножеств
`n!`	ещё быстрее	все перестановки	перебор порядков

Граница n³ | 2ⁿ - граница между ростом степени и ростом экспоненты, а не абсолютное «выполнимо | невыполнимо»: при малом n перебор 2ⁿ выполним, при огромном n и n³ неподъёмен. Но с ростом n экспонента обгоняет любую степень: степень растёт от основания, экспонента - от показателя.

Дерево решений: чем оценивать

Вопрос	Инструмент
Сколько шагов точно?	`T(n)` построчно: цена × число выполнений
Как записать порядок строго?	`O` (потолок), `Ω` (пол), `Θ` (коридор), через `c` и `n₀`
Как доказать принадлежность классу?	предъявить `c` и `n₀`; опровергнуть - показать, что их нет
Как свернуть сумму из цикла?	арифметический / геометрический / гармонический ряд
Сумма не сворачивается?	оценить интегралом: `Σ f(k)` порядка `∫ f(x)dx`
Какой вход берём?	по умолчанию худший (гарантия); средний - ожидание
Сколько памяти?	вспомогательная (сверх входа); стек рекурсии = глубина

Правила обращения (одной строкой)

Множитель-константа выбрасывается (c·f = Θ(f)). Сумма равна старшему слагаемому (f + g = Θ(max)). Независимая вложенность перемножается. Складывают функции, перемножают только вложенные циклы.

Связи с остальным курсом

Сортировки - здесь весь аппарат: n·log n против n², худший и средний случай, память слияния против быстрой сортировки.

Рекуррентности берут дерево вызовов и суммы отсюда: T(n) = 2T(n/2) + n решается через сумму по уровням.

Хеширование держится на рандомизированном среднем: случайное зерно уводит худший случай из-под контроля противника.

Все последующие разделы оценивают свои алгоритмы этим языком: O/Θ, ряды, худший случай, вспомогательная память - дальше это фон, а не тема.

Чек-лист: объясни своими словами

Как из кода получить T(n) построчно и почему проверка цикла даёт n+1.
Что такое O, Ω, Θ через c и n₀ и почему Θ = O и Ω.
Почему n = O(n²) истинно, а n² = O(n) - нет.
Три правила обращения и почему сумму заменяют максимумом, а не суммой порядков.
Три ряда (арифметический, геометрический, гармонический) и их порядок.
Как оценить Σ k² интегралом и почему выходит n³.
Чем худший случай отличается от среднего и почему по умолчанию берут худший.
Два «в среднем»: по входам и по монетке - какое защищает от враждебного входа.
Что такое вспомогательная память и почему стек рекурсии в неё входит.
Где на лестнице порядков граница «выполнимо / невыполнимо» и почему.

Что дальше

Правильность доказана (раздел 1), стоимость измеряется (этот раздел). Дальше - рекуррентности: как оценивать алгоритмы, которые вызывают сами себя, деревом вызовов и суммой по уровням, а потом - первый большой класс алгоритмов, сортировки, где весь этот аппарат заработает разом.