Алгоритмы и Big-O

Что это такое

Big-O — короткая запись того, как растёт стоимость алгоритма вместе с его входом. Константы и железо при этом отбрасываются, и остаётся простой вопрос: если вход удвоился, работа удвоится, учетверится или почти не изменится? Алфавит ответов — константа, логарифм, линейный рост, линейно-логарифмический, квадрат, экспонента — мал настолько, что помещается в голове, и достаточно точен, чтобы сказать, какая из двух конструкций выдержит настоящие данные.

Почему это важно

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

Что в этом треке

Как растёт стоимость (Big-O) (01-cs-fundamentals/14-algorithms-big-o/01-how-cost-grows-big-o) — чтение скоростей роста и выбор записи, которая честно описывает алгоритм.
Сортировка, поиск и обход (01-cs-fundamentals/14-algorithms-big-o/02-sorting-searching-and-traversal) — стандартные процедуры и та стоимость, которую несёт каждая из них.

Предварительные требования

Структуры данных (01-cs-fundamentals/02-data-structures)

Что читать дальше

Псевдокод (01-cs-fundamentals/07-pseudocode) — записать алгоритм обычным языком, прежде чем судить о том, как он растёт.
Операционные системы (01-cs-fundamentals/15-operating-systems) — во что обходится шаблон доступа к памяти за алгоритмом на настоящем железе.
Внутреннее устройство баз данных (01-cs-fundamentals/04-database-internals) — где сортировку и поиск делают за вас и почему запись всё равно применима.