Справочные ресурсы

Краткий справочник по сложности операций со структурами данных

Структура данныхВставкаDeleteПоискОбход
МассивO(n) середина / O(1) конецO(n) середина / O(1) конецO(1) по индексу / O(n) по значениюO(n)
Односвязный списокO(1) голова / O(n) хвостO(1) голова / O(n) заданная позицияO(n)O(n)
Двусвязный списокO(1) (известная позиция)O(1) (известная позиция)O(n)O(n)
СтекO(1)O(1)——
ОчередьO(1)O(1)——
Очередь с приоритетом (куча)O(log n)O(log n)——
Бинарное дерево (BST)O(log n)~O(n)O(log n)~O(n)O(log n)~O(n)O(n)
Хеш-таблицаO(1) в среднемO(1) в среднемO(1) в среднем—
КучаO(log n)O(log n)O(1) вершина кучи—
ГрафO(1) список смежностиO(E)O(V+E) DFS/BFSO(V+E)

Краткий справочник по алгоритмам сортировки

АлгоритмСредняя сложностьСложность в худшем случаеПамятьУстойчиваяОднострочник
ПузырьковаяO(n²)O(n²)O(1)ДаПростая, но медленная, подходит для обучения
ВыборомO(n²)O(n²)O(1)нетМинимум обменов
ВставкаO(n²)O(n²)O(1)ДаОптимальна для небольших объёмов или почти отсортированных данных
БыстраяO(n log n)O(n²)O(log n)нетУниверсальный первый выбор, умная идея разбиения
СлияниемO(n log n)O(n log n)O(n)ДаСтабильная производительность, но требует дополнительной памяти
Пирамидальная сортировкаO(n log n)O(n log n)O(1)нетСортировка на месте, оптимальное использование памяти
ШеллаO(n^1.3)O(n²)O(1)нетУлучшенная версия сортировки вставками

Ранжирование сложности Big O

Сложностьn=10n=1000n=1000000Оценка
O(1)111Оптимально
O(log n)~3~10~20Отличный
O(n)1010001000000Приемлемо
O(n log n)~30~10000~20000000Удовлетворительно
O(n²)100100000010¹²Будьте осторожны
O(2ⁿ)1024Астрономическое числоНевозможноНепригодно

Рекомендуемые учебные ресурсы

TypeNameОписание
Классический учебник«Структуры данных (издание на языке C)» Янь ВэйминяСтандартный учебник для китайских вузов, всеобъемлющая система
Классический учебник"Введение в алгоритмы" (CLRS)Авторитетный справочник в области алгоритмов, глубокое и систематическое изложение
Онлайн-практикаLeetCode (leetcode.com)Огромное количество алгоритмических задач, лучший выбор для подготовки к собеседованиям
Онлайн-практикаNowcoder (nowcoder.com)Китайская платформа для практики собеседований, подходит для подготовки к набору выпускников
Инструмент визуализацииVisualgo (visualgo.net)Визуализация алгоритмов, помогает понять процесс выполнения
Онлайн-компиляторCompiler Explorer (godbolt.org)Просмотр ассемблера после компиляции кода C, понимание внутренних деталей
Другие расширения