Сложность операций с коллекциями и выбор структуры

↑ 1.5 Коллекции и основы LINQ · ← Предыдущая

Обязательно~5 мин чтенияУровень: junior

Зачем это на собесе

«Какая сложность у поиска в списке и в словаре?» и «Что выберете для этой задачи?» — стандартные вопросы. Ждут не заученной таблицы, а умения сопоставить операции с нагрузкой: что чаще, чтение или вставка, нужен ли порядок, есть ли параллельный доступ.

Объяснение

Нотация O

Описывает рост числа операций при росте n, отбрасывая константы. Порядок роста: O(1) < O(log n) < O(n) < O(n log n) < O(n²). Амортизированная сложность — усреднённая по серии операций (добавление в List в конце: иногда O(n), в среднем O(1)).

Таблица сложностей (среднее, если не сказано иное)

Структура	Доступ по индексу/ключу	Поиск значения	Вставка	Удаление	Порядок
T[]	O(1)	O(n)	— (фикс. размер)	—	по индексу
List<T>	O(1)	O(n)	конец: O(1) амортиз.; середина: O(n)	O(n)	по индексу
LinkedList<T>	O(n)	O(n)	по узлу: O(1)	по узлу: O(1)	порядок вставки
Dictionary<K,V>	O(1) по ключу	O(n) по значению	O(1)	O(1)	не гарантирован
HashSet<T>	—	O(1)	O(1)	O(1)	не гарантирован
SortedDictionary/SortedSet	O(log n)	O(log n)	O(log n)	O(log n)	по ключу
Queue<T>	Peek: O(1)	O(n)	Enqueue: O(1)	Dequeue: O(1)	FIFO
Stack<T>	Peek: O(1)	O(n)	Push: O(1)	Pop: O(1)	LIFO
PriorityQueue	Peek: O(1)	O(n)	O(log n)	Dequeue: O(log n)	по приоритету

Худший случай для хэш-таблиц — O(n) при массовых коллизиях (плохой GetHashCode).

Как выбирать структуру

• Нужен доступ по индексу и перебор → List<T> / массив.
• Быстрый поиск по ключу → Dictionary.
• Уникальность и проверка «есть ли» → HashSet.
• Всегда отсортированные данные и диапазонные запросы → SortedDictionary/SortedSet.
• Очередь задач → Queue; откат/DFS → Stack; «самый приоритетный» → PriorityQueue.
• Много потоков → ConcurrentDictionary, ConcurrentQueue, Channel<T>.
• Данные не меняются после загрузки → FrozenDictionary/FrozenSet/ImmutableArray (быстрее чтение).

Типичные оптимизации

// Плохо: O(n·m) — для каждого заказа линейный поиск клиента
foreach (var o in orders)
{
    var c = customers.First(x => x.Id == o.CustomerId);
}
 
// Хорошо: O(n + m)
var byId = customers.ToDictionary(c => c.Id);
foreach (var o in orders)
{
    var c = byId[o.CustomerId];
}

// Проверка вхождения в цикле: список -> множество
var blocked = new HashSet<Guid>(blockedList);
var allowed = users.Where(u => !blocked.Contains(u.Id));

Не только Big-O

• Локальность кэша: массив и List быстрее связных структур, потому что данные лежат подряд.
• Аллокации и GC: структуры с узлами (LinkedList, деревья) создают много объектов.
• Константы: для малых n (десятки элементов) линейный поиск по List может быть быстрее хэш-таблицы.
• Измеряйте: BenchmarkDotNet вместо догадок.

Нюансы и подводные камни

• List<T>.Remove/Contains/IndexOf — O(n): в горячем цикле по большим данным это O(n²).
• LinkedList обычно проигрывает List даже там, где «теоретически» выигрывает.
• Порядок перебора Dictionary/HashSet не гарантирован: если порядок нужен, используйте List, SortedX или OrderedDictionary (.NET 9).
• Плохой GetHashCode (постоянное значение, малое число различных хэшей) превращает словарь в список.
• string.Contains и конкатенация в циклах тоже дают скрытые квадратичные затраты.
• «Преждевременная оптимизация»: сначала выберите понятную структуру, оптимизируйте после профилирования.

Практика

• Оценить сложность вложенных циклов и LINQ-запросов в своём проекте и заменить один First внутри цикла на словарь.
• Сравнить List.Contains и HashSet.Contains на 10, 1 000 и 1 000 000 элементов через BenchmarkDotNet.
• Реализовать очередь с приоритетами на PriorityQueue для планировщика задач.

Вопросы с ответами

Какая сложность поиска в List<T> и в Dictionary<K,V>?

В List поиск значения — O(n), доступ по индексу O(1). В Dictionary поиск по ключу в среднем O(1), в худшем O(n) при коллизиях.

Что такое амортизированная сложность?

Средняя стоимость операции по длинной серии. Добавление в List в конец иногда O(n) (рост буфера), но в среднем O(1).

Как ускорить проверку принадлежности элемента большому набору?

Хранить набор в HashSet<T> вместо List<T>: Contains становится O(1) вместо O(n).

Почему LinkedList<T> редко быстрее List<T>?

Вставка O(1) возможна только по уже найденному узлу, поиск O(n), а узлы разбросаны в памяти и создают нагрузку на GC. List использует непрерывный блок и хорошо ложится в кэш процессора.

Когда SortedDictionary лучше Dictionary?

Когда нужен постоянный порядок по ключу или диапазонные запросы. Цена: O(log n) на операции вместо O(1).

Связанные темы

• Предыдущая: LINQ: основные операторы · Следующий раздел (этап 2): Этап 2 · C♯ глубоко и .NET runtime
• Коллекции: Массивы, List, Dictionary, HashSet, Queue, Stack
• Алгоритмы и структуры данных на C#: 8.5 Алгоритмы и структуры данных на C♯
• Производительность .NET: 7.1 Производительность .NET и кэширование