массив

SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи SRT Алгоритм Простые сортировки Вставки, выбор и пузырёк: квадратичные, но вставки работают внутри библиотечных сортировок. O(n²) 2 задачи SRT Алгоритм Сортировка слиянием Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти. O(n log n) 2 задачи SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи SRT Алгоритм Сортировка подсчётом и поразрядная Без сравнений: посчитать ключи или разложить их по цифрам — O(n + k) и O(d·n) вместо n log n. O(n + k) и O(d·(n + b)) 2 задачи SRT Алгоритм Перемешивание Фишера — Йетса Честная случайная перестановка за O(n): каждая из n! — с вероятностью 1/n!, и почему «обмен с любым» нечестен. O(n) 2 задачи DS Структура данных Динамический массив Массив, который растёт сам: доступ по индексу за O(1), добавление в конец — за O(1) амортизированно. O(1) амортизированно на append 2 задачи DS Структура данных Связный список Узлы со ссылками на соседей: вставка и удаление у известного узла за O(1), путь к k-му — k шагов. O(1) у известного узла 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Приём Монотонный стек Стек с упорядоченными значениями: ближайший больший элемент и наибольший прямоугольник за O(n). O(n) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево. соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков 2 задачи DP Алгоритм Наибольшая возрастающая подпоследовательность Самая длинная растущая цепочка элементов в исходном порядке: пасьянс и двоичный поиск за n log n. O(n log n) 2 задачи NUM Алгоритм Решето Эратосфена Все простые до n за O(n log log n): вычёркиваем кратные каждого простого, начиная с его квадрата. O(n log log n) 2 задачи NUM Алгоритм Длинная арифметика Числа длиннее машинного слова: цифры по основанию 10⁹ или 2³⁰, переносы, столбик и дорогая печать. сложение O(n), умножение и деление столбиком O(n²), печать в десятичной записи O(n²) или O(M(n) log n) 2 задачи NUM~ Приём Суммирование Кэхэна Сложить миллионы дробных чисел и не растерять младшие разряды: поправка Кэхэна, попарное и точное суммирование. O(n) 1 задача TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи TEC Приём Данные, удобные кэшу Тот же алгоритм, другой порядок обращений к памяти: обход блоками, запас в строках и раскладка по полям. O-большое то же 1 задача TEC Приём Два указателя Два индекса движутся только вперёд и заменяют перебор пар или отрезков одним проходом за O(n). O(n) 2 задачи TEC Приём Векторизация Вынести цикл из интерпретатора в операции над целыми массивами: что ускоряется в сотни раз и что не векторизуется. та же O(n), что у цикла 2 задачи TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи TEC Приём Как выбрать структуру данных Сначала список операций, потом структура: стоимость каждой операции в Python и Go на одной карте. зависит от выбора 1 задача TEC Приём Сколько займёт в памяти Байты на запись — и сразу видно, поместится ли миллиард: из чего складывается вес данных в Python и Go. прикидка — байты на запись × число записей 1 задача TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи