амортизация

Статьи

SRT Алгоритм Timsort Находит готовые упорядоченные куски и сливает их: стек серий, галоп, powersort. O(n log n), на готовых данных O(n) 2 задачи DS Структура данных Динамический массив Массив, который растёт сам: доступ по индексу за O(1), добавление в конец — за O(1) амортизированно. O(1) амортизированно на append 2 задачи DS Структура данных Стек и очередь Стек: последним пришёл — первым ушёл. Очередь: первым пришёл — первым ушёл. Каждая операция — O(1). O(1) на push и pop, enqueue и dequeue 2 задачи DS Структура данных Верёвка Текст кусками в листьях дерева: вставка и удаление в середине — путь к листу и один кусок; номер строки — по счётчикам в узлах. O(log n + C) на вставку, удаление, доступ 1 задача DS Структура данных Косое дерево После каждого запроса ключ поднимается в корень парами поворотов: частые ключи сами собираются наверху, амортизированно O(log n). O(log n) амортизированно на операцию; одна операция — до O(n) 1 задача DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи STR Алгоритм Префикс-функция и КМП Все вхождения образца за O(n + m) без шагов назад по тексту; префикс-функция находит и период строки. O(n + m) 2 задачи STR Алгоритм Z-функция Сколько букв от каждой позиции совпадает с началом строки — за O(n); поиск, периоды и повторы подряд. O(n) 2 задачи STR Алгоритм Алгоритм Манакера Все палиндромы строки за O(n): зеркало внутри самого правого палиндрома; фаги и палиндромы в их ДНК. O(n) 2 задачи SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым.

запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень

2 задачи TEC Приём Быстрый ввод и вывод Миллион чисел за десятки миллисекунд вместо секунды: чтение целиком, буфер и одна запись вывода. O(размер входа) 1 задача TEC Приём Амортизационный анализ Оценка всей последовательности операций, а не каждой: суммой, монетами и потенциалом — и где она не спасает. оценка на последовательность 2 задачи

Задачи

Как растёт список Python Счётчик туда-обратно Палиндром из букв Палиндромы в ДНК Самое сильное за месяц Склад-гармошка Цена журнала

Часто рядом

классика 9 собеседования 6 в проде 4 массив 4 олимпиады 4 стек 3 редакторы текста 3 поиск в тексте 3 биоинформатика 3 сортировка 2 очередь 2 дерево 2