Big O и коллекции .NET
↑ 8.5 Алгоритмы и структуры данных на C♯ · → Следующая
Зачем это на собесе
Оценка сложности и выбор коллекции — база любой алгоритмической задачи.
Объяснение
Big O описывает рост времени/памяти при увеличении входа n (в худшем случае, без констант).
| Класс | Пример | n = 10⁶ |
|---|---|---|
| O(1) | доступ по индексу, Dictionary | 1 |
| O(log n) | бинарный поиск, SortedSet | 20 |
| O(n) | линейный проход | 10⁶ |
| O(n log n) | эффективная сортировка | 2·10⁷ |
| O(n²) | вложенные циклы | 10¹² (неприемлемо) |
| O(2ⁿ), O(n!) | перебор подмножеств/перестановок | только для малых n |
Коллекции .NET:
| Коллекция | Доступ/поиск | Вставка | Удаление | Заметки |
|---|---|---|---|---|
T[] | O(1) по индексу, O(n) поиск | — | — | фиксированный размер |
List<T> | O(1) по индексу | O(1) в конец амортиз., O(n) в середину | O(n) | динамический массив |
LinkedList<T> | O(n) | O(1) при известном узле | O(1) при известном узле | редко нужен |
Dictionary<K,V> | O(1) средн. | O(1) | O(1) | хэш-таблица, порядок не гарантирован |
HashSet<T> | O(1) | O(1) | O(1) | уникальность |
SortedDictionary/SortedSet | O(log n) | O(log n) | O(log n) | красно-чёрное дерево |
Queue<T>/Stack<T> | — | O(1) | O(1) | FIFO / LIFO |
PriorityQueue<T,P> | Peek O(1) | O(log n) | O(log n) | двоичная куча |
ImmutableX | копирование при изменении |
Амортизированная сложность: добавление в List<T> в среднем O(1), хотя иногда O(n) при расширении массива (удвоение).
Пространственная сложность: дополнительная память алгоритма (рекурсия — глубина стека).
Нюансы и подводные камни
- Константы важны на практике: O(n) с тяжёлым телом может быть медленнее O(n log n) на малых n.
ContainsуList<T>— O(n): для частых проверок используйтеHashSet.string +=в цикле — O(n²) из-за копирования.- Хэш-коллизии и плохой
GetHashCodeвырождаютDictionaryв O(n). - LINQ
Count()наIEnumerableможет перечислять всё.
Практика
- Определите сложность кода из 5 фрагментов с вложенными циклами.
- Замените
List.ContainsнаHashSetи измерьте. - Выберите коллекцию для очереди задач по приоритету.
Вопросы с ответами
Что такое амортизированная сложность?
Средняя стоимость операции по длинной последовательности; добавление в
List<T>дорого редко и в среднем O(1).
Почему Dictionary O(1)?
Хэш ключа определяет корзину напрямую; при малом числе коллизий поиск не зависит от размера.