Вопросы по сложности алгоритмов (Big O), базовым структурам данных, поиску, сортировке и стратегиям решения задач.
Big O описывает верхнюю границу сложности алгоритма по времени выполнения (Time Complexity) или используемой памяти (Space Complexity) в худшем случае в зависимости от размера входных данных `N`. **Основные классы сложности**: * `O(1)`: Константное время. Время не зависит от размера данных (например, получение элемента массива по индексу). * `O(log N)`: Логарифмическое время. На каждом шаге размер задачи уменьшается вдвое (например, бинарный поиск). * `O(N)`: Линейное время. Время растет пропорционально размеру данных (например, простой поиск в массиве). * `O(N log N)`: Линейно-логарифмическое время. Характерно для эффективных сортировок (Merge Sort, Quick Sort). * `O(N^2)`: Квадратичное время. Характерно для простых сортировок пузырьком или вложенных циклов.
Бинарный поиск ищет элемент в **отсортированном** массиве: 1. Берется средний элемент массива. 2. Если средний элемент равен искомому — поиск завершен. 3. Если искомый элемент меньше среднего — алгоритм повторяет поиск в левой половине массива. 4. Если больше — в правой. 5. Процесс повторяется, пока подмассив не станет пустым. * **Сложность**: По времени — `O(log N)`, по памяти — `O(1)` (при итеративной реализации).
* **Стек (Stack)**: Работает по принципу LIFO (Last-In, First-Out — последним пришел, первым ушел). Основные операции: `push` (добавить на вершину) и `pop` (удалить с вершины). Обе операции занимают `O(1)`. * **Очередь (Queue)**: Работает по принципу FIFO (First-In, First-Out — первым пришел, первым ушел). Основные операции: `enqueue` (добавить в конец) и `dequeue` (удалить из начала). Обе операции занимают `O(1)`.
Хэш-таблица сопоставляет ключи со значениями с помощью хэш-функции, переводящей ключ в индекс массива. * **Коллизия**: Ситуация, когда два разных ключа дают одинаковый хэш-индекс. * **Разрешение коллизий**: 1. **Метод цепочек (Chaining)**: Каждая ячейка массива содержит указатель на связанный список элементов с одинаковым хэшем. 2. **Открытая адресация (Open Addressing)**: При коллизии ищется другая свободная ячейка по определенному правилу (линейное пробирование, квадратичное пробирование, двойное хэширование).
* **DFS (Depth-First Search — поиск в глубину)**: Идет максимально глубоко по одной ветви дерева, прежде чем перейти к соседней. Реализуется с помощью рекурсии или явного использования стека. Потребляет меньше памяти для узких глубоких деревьев. * **BFS (Breadth-First Search — поиск в ширину)**: Обходит дерево по уровням (сначала все дочерние узлы текущего уровня, затем их дети). Реализуется с помощью очереди. Полезен для поиска кратчайшего пути в невзвешенном графе.
Quick Sort использует стратегию «разделяй и властвуй»: 1. Выбирается опорный элемент (pivot). 2. Массив перегруппировывается: элементы меньше опорного перемещаются влево, больше — вправо. 3. Алгоритм рекурсивно запускается для левой и правой частей. * **Сложность**: * В среднем и лучшем случае: `O(N log N)`. * В худшем случае (когда массив уже отсортирован, а в качестве pivot выбирается крайний элемент): `O(N^2)`. Для избежания худшего случая pivot выбирают случайно.
Это бинарные деревья поиска, которые автоматически сохраняют свою высоту минимальной (около `log N`) после операций вставки и удаления с помощью операций вращения ветвей. Это гарантирует, что поиск, вставка и удаление всегда будут выполняться за стабильные `O(log N)` времени, исключая вырождение дерева в связанный список.
Алгоритм Дейкстры находит кратчайшие пути от одной из вершин графа до всех остальных в ориентированном или неориентированном графе с **неотрицательными** весами ребер. Он пошагово выбирает ближайшую непосещенную вершину, обновляет расстояния до ее соседей (релаксация ребер) и помечает вершину как посещенную.
Динамическое программирование — это метод решения сложных задач путем разбиения их на перекрывающиеся подзадачи, решения каждой подзадачи ровно один раз и сохранения ответов. * **Мемоизация (Top-Down)**: Нисходящий подход. Решение пишется рекурсивно, но результаты вызовов кэшируются (например, вычисление чисел Фибоначчи с массивом результатов). * **Табуляция (Bottom-Up)**: Восходящий подход. Решение строится итеративно, заполняя таблицу результатов от базовых случаев к сложным (исключает переполнение стека вызовов рекурсии).
Паттерн использует два индекса (указателя) для прохода по структуре данных (обычно отсортированному массиву) навстречу друг другу или в одном направлении. Позволяет находить пары элементов с определенной суммой, удалять дубликаты или находить подстроки за линейное время `O(N)` без вложенных циклов.
Паттерн используется для эффективного поиска подмассивов или подстрок в массиве или строке. Вместо повторного перебора элементов для каждого подмассива, окно данных сдвигается вправо, добавляя один элемент справа и удаляя один слева, что снижает сложность с `O(N^2)` до `O(N)`.
Алгоритм использует два указателя, движущихся по связанному списку с разной скоростью: * «Черепаха» смещается на 1 узел за шаг. * «Заяц» смещается на 2 узла за шаг. * Если в списке есть цикл, «заяц» обязательно догонит «черепаху» и они встретятся на одном узле. Если цикла нет, «заяц» первым достигнет конца списка (`nil`). Сложность: по времени — `O(N)`, по памяти — `O(1)`.
Префиксное дерево (Trie) — это древовидная структура данных, используемая для эффективного хранения и быстрого поиска строк по префиксам (например, автодополнение текста). Каждое ребро дерева соответствует одному символу, а путь от корня к узлу задает строку или префикс.
* **Стабильная сортировка**: Сохраняет исходный взаимный порядок элементов с одинаковыми ключами. Пример: Сортировка слиянием (Merge Sort), сортировка вставками. * **Нестабильная сортировка**: Может изменить исходный порядок одинаковых элементов. Пример: Быстрая сортировка (Quick Sort), пирамидальная сортировка (Heap Sort).
Бинарная куча — это сбалансированное бинарное дерево, удовлетворяющее свойству кучи: значение родителя всегда больше (Max-Heap) или меньше (Min-Heap) значений его детей. * **Сложность**: * Получение корня (мин/макс): `O(1)`. * Вставка и удаление элемента: `O(log N)` (требует восстановления свойств кучи путем просеивания вверх или вниз). * Построение кучи из массива: `O(N)`.
Жадный алгоритм на каждом шаге делает локально оптимальный выбор в надежде, что это приведет к глобально оптимальному решению. Он не пересчитывает прошлые шаги. Пример: Алгоритм Хаффмана для сжатия данных, выбор монет минимального количества для выдачи сдачи (при стандартных номиналах).
Алгоритм основывается на том, что для вычисления `a^n`: * Если `n` четное: `a^n = (a^(n/2))^2`. * Если `n` нечетное: `a^n = a * a^(n-1)`. Это позволяет сократить количество умножений с линейных `N` до логарифмических `log N`.
* **Массив**: Элементы хранятся в непрерывном блоке памяти друг за другом. Это обеспечивает высокую локальность кэша процессора и доступ за `O(1)` по индексу. * **Связанный список**: Элементы (узлы) могут быть разбросаны по всей оперативной памяти и связаны ссылками. Это требует больше памяти под указатели и ухудшает локальность кэша (много промахов кэша), но позволяет вставлять элементы в начало за `O(1)`.
Разреженная таблица — это структура данных, позволяющая отвечать на запросы о минимуме/максимуме на отрезке статического массива (Range Minimum Query) за константное время `O(1)` после предобработки за `O(N log N)`. Строится на основе степеней двойки.
Коллизия хэш-функции второго рода (или поиск прообраза) — это ситуация, когда для заданного значения хэша `H` математически подбирается такое входное значение `X2`, что `hash(X2) = H`. В криптографии хэш-функции должны быть устойчивы к поиску прообраза.
Merge Sort делит массив пополам, рекурсивно сортирует каждую половину, а затем сливает две отсортированные половины в один упорядоченный массив. * **Сложность**: По времени — всегда `O(N log N)` (лучший, средний и худший случай). По памяти — `O(N)` (требуется дополнительный массив для слияния).
Граф — это структура данных, состоящая из вершин и соединяющих их ребер. * **Матрица смежности**: Двумерный массив размером `V x V` (где V — число вершин), где ячейка `[i][j]` указывает на наличие ребра. Плюс — проверка ребра за `O(1)`. Минус — тратит `O(V^2)` памяти, неэффективно для разреженных графов. * **Список смежности**: Массив списков, где для каждой вершины хранится список ее соседей. Плюс — тратит `O(V + E)` памяти (эффективно). Минус — проверка наличия ребра требует перебора списка соседей.
Топологическая сортировка упорядочивает вершины ориентированного ациклического графа (DAG) так, что для любого ребра `(u, v)` вершина `u` идет перед `v`. Реализуется с помощью DFS (вершина добавляется в результирующий стек после обхода всех ее потомков) или алгоритма Кана (на основе степеней входящих ребер вершин).
Красно-черное дерево — это самобалансирующееся бинарное дерево поиска, где каждый узел хранит дополнительный бит цвета (красный или черный). Балансировка поддерживается набором правил о цветах при вставках и удалениях, гарантируя, что высота дерева не превышает `2 * log(N + 1)`.
Алгоритм KMP ищет вхождения шаблона в строке за линейное время `O(N + M)`. Он избегает повторного сравнения символов при несовпадении, используя префикс-функцию шаблона (вычисляемую заранее), которая указывает, на сколько символов можно сдвинуть шаблон вперед.
Дерево отрезков — это структура данных для эффективного выполнения запросов суммы/минимума на отрезках массива и изменения элементов за `O(log N)`. Представляет собой бинарное дерево, где каждый узел хранит агрегированное значение для определенного интервала массива.
Quickselect находит K-й по величине элемент в неотсортированном массиве без полной сортировки. Работает аналогично Quick Sort: выбирается pivot, массив делится на две части. Но рекурсивный поиск продолжается только в одной из половин (где должен находиться K-й элемент). Среднее время — `O(N)`.
Бинарный подъем — это метод нахождения предков в дереве (например, поиск наименьшего общего предка — LCA). Для каждого узла заранее вычисляются предки на расстояниях степеней двойки (1, 2, 4, 8...), что позволяет подниматься вверх по дереву на любую высоту за `O(log N)`.
DSU (или Union-Find) — структура данных, которая объединяет элементы в множества и определяет, находятся ли два элемента в одном множестве. С оптимизациями (сжатие путей и ранговая эвристика) обе операции выполняются практически за константное время `O(alpha(N))`.
Алгоритм Косарайю находит компоненты сильной связанности в ориентированном графе за два прохода DFS (второй проход выполняется на транспонированном графе в порядке времени выхода вершин первого прохода). Сложность — `O(V + E)`.
Бинарный поиск используется для поиска элемента в **отсортированном** массиве. * **Принцип**: Алгоритм сравнивает искомое значение со средним элементом массива. Если они равны, поиск завершен. Если искомое меньше среднего, поиск продолжается в левой половине массива, иначе — в правой. На каждом шаге область поиска сокращается вдвое. * **Сложность**: В лучшем случае — `O(1)`, в среднем и худшем — `log₂N` сравнений, то есть временная сложность составляет `O(log N)`. Пространственная сложность — `O(1)` для итеративного подхода.
Хэш-таблица сопоставляет ключи со значениями с помощью хэш-функции, вычисляющей индекс в массиве бакетов. **Решение коллизий** (когда разные ключи имеют одинаковый хэш): 1. **Метод цепочек (Chaining)**: Каждая ячейка массива содержит указатель на связанный список или дерево элементов с одинаковым хэшем. При коллизии элемент просто добавляется в список. 2. **Открытая адресация (Open Addressing)**: Все элементы хранятся непосредственно в таблице. При коллизии ищется свободная ячейка по определенному правилу (линейное пробирование, квадратичное пробирование, двойное хэширование).
* **BFS (Breadth-First Search)**: Обходит дерево по уровням (горизонтально). Сначала посещаются все узлы текущей глубины, затем следующей. Использует структуру данных **Очередь (Queue)**. Подходит для поиска кратчайшего пути в невзвешенных графах. * **DFS (Depth-First Search)**: Идет вглубь одной ветви до упора, затем возвращается (backtracking) и проверяет другие ветви. Использует **Стек (Stack)** или рекурсию. Подходит для топологической сортировки, поиска циклов и проверки связности.
Quick Sort (быстрая сортировка) работает по принципу «разделяй и властвуй»: 1. Выбирается опорный элемент (pivot). 2. Массив перегруппировывается: элементы меньше pivot перемещаются влево, больше — вправо. 3. Рекурсивно сортируются левая и правая части. * **Средняя сложность**: `O(N log N)`. * **Худшая сложность (`O(N^2)`)**: Возникает, когда на каждом шаге массив делится крайне несбалансированно (например, если массив уже отсортирован, а в качестве pivot всегда выбирается самый крайний элемент). Для предотвращения этого pivot выбирают случайно или используют медиану трех чисел.
Динамическое программирование — метод решения сложных задач путем их разбиения на более простые перекрывающиеся подзадачи, результаты которых сохраняются для избежания повторных вычислений. * **Мемоизация (Top-Down)**: Рекурсивное решение сверху вниз с сохранением результатов в кэш (например, вычисление чисел Фибоначчи с массивом результатов). * **Табуляция (Bottom-Up)**: Итеративное решение снизу вверх, заполняющее таблицу переходов от базовых случаев к целевому (обычно использует массивы или матрицы).
Алгоритм Дейкстры находит кратчайшие пути от одной из вершин графа до всех остальных во взвешенном графе с неотрицательными весами ребер. * **Принцип**: Поддерживается массив текущих кратчайших расстояний. На каждом шаге выбирается еще не посещенная вершина с минимальным расстоянием. Для нее проводится релаксация ребер: проверяется, нельзя ли улучшить расстояние до ее соседей, пройдя через нее. Посещенная вершина фиксируется. * Для оптимизации выбора вершины с минимальным весом используется двоичная куча (очередь с приоритетом), что дает сложность `O(E log V)`.
Метод двух указателей оптимизирует перебор элементов массива, сокращая сложность с `O(N^2)` до `O(N)`. Указатели могут двигаться навстречу друг другу (например, для проверки палиндрома или поиска пары чисел с заданной суммой в отсортированном массиве) или в одном направлении с разной скоростью (быстрый и медленный указатели).
Этот метод используется для поиска подмассива или подстроки, удовлетворяющих определенным условиям. Вместо повторного сканирования подмассивов вложенными циклами (`O(N^2)`), мы поддерживаем «окно» с левой и правой границами. Правая граница расширяет окно, добавляя элементы, а левая — сжимает его при нарушении условий, что позволяет решить задачу за один проход `O(N)`.
Префиксное дерево (Trie) — древовидная структура данных, используемая для эффективного хранения и поиска строк (ключей). Каждый узел дерева представляет собой символ строки. Путь от корня до узла формирует префикс строки. * **Применение**: Автодополнение поисковых запросов, проверка орфографии, T9. * **Плюс**: Поиск слова длины L занимает `O(L)`, что не зависит от общего количества слов в базе.
Алгоритм Флойда (метод «черепахи и зайца») использует два указателя, которые одновременно начинают движение с головы списка: * Медленный (`slow`) сдвигается на 1 узел за шаг. * Быстрый (`fast`) сдвигается на 2 узла за шаг. Если в списке нет цикла, быстрый указатель достигнет конца (`nil`). Если цикл есть, быстрый указатель догонит медленный внутри цикла, и они укажут на один и тот же элемент. Сложность: по памяти `O(1)`, по времени `O(N)`.
* **Stack**: LIFO (Last In, First Out). Элементы добавляются и извлекаются с одного конца. * **Queue**: FIFO (First In, First Out). Вставка в конец, извлечение из начала. * **Реализация очереди через два стека**: 1. Стек `InStack` используется для добавления элементов (метод `enqueue`). 2. Стек `OutStack` используется для извлечения (метод `dequeue`). Если `OutStack` пуст, мы перекладываем (pop -> push) все элементы из `InStack` в `OutStack` (порядок элементов при этом переворачивается) и забираем верхний элемент.
Двоичная куча — это почти полное бинарное дерево, удовлетворяющее свойству кучи: значение в любом родительском узле всегда не меньше (Max-Heap) или не больше (Min-Heap) значений его потомков. Обычно хранится в виде массива. * **Heap Sort (пирамидальная сортировка)**: 1. Из исходного массива строится куча Max-Heap за `O(N)`. 2. Максимальный элемент (корень кучи) меняется местами с последним элементом массива. 3. Размер кучи уменьшается на 1, корень восстанавливает свойства кучи (sift-down). 4. Шаги 2-3 повторяются, пока размер кучи не станет равен 1. Сложность сортировки: `O(N log N)` в любых случаях, по памяти `O(1)`.
Оба дерева являются самобалансирующимися бинарными деревьями поиска: * **AVL-дерево**: Имеет более строгую балансировку (высота левого и правого поддеревьев отличается максимум на 1). За счет этого поиск в нем выполняется быстрее. Однако операции вставки и удаления требуют больше вращений для восстановления баланса. * **Красно-черное дерево**: Имеет более мягкую балансировку. Поиск работает немного медленнее, чем в AVL, но вставка и удаление происходят быстрее за счет меньшего количества вращений. Используется в стандартных коллекциях (например, `TreeMap` в Java, `std::map` в C++).
Амортизационная сложность — это среднее время, затрачиваемое на операцию в худшем случае при ее многократном повторении. * **Пример**: Добавление элемента в динамический массив. В большинстве случаев добавление занимает `O(1)`, так как в массиве есть свободное место. Но когда массив заполнен, происходит перевыделение памяти и копирование всех N элементов, что занимает `O(N)`. Поскольку это копирование происходит редко (при удвоении размера), среднее время на одну операцию добавления остается равным `O(1)`.
Алгоритм KMP ищет подстроку в строке за линейное время `O(N + M)` без откатов назад по исходному тексту. * **Принцип**: Предварительно вычисляется префикс-функция (массив пи) для искомого шаблона, которая хранит длину наибольшего собственного префикса, являющегося также суффиксом. При несовпадении символов алгоритм использует префикс-функцию, чтобы сдвинуть шаблон вперед на безопасное расстояние, избегая повторного сравнения уже совпавших символов.
Sparse Table — статическая структура данных для решения задач RMQ (Range Minimum Query — поиск минимума на отрезке) без изменения элементов. * **Принцип**: Таблица предварительно рассчитывает ответы для всех отрезков, длина которых является степенью двойки (`2^k`). * **Сложность**: Предподсчет занимает `O(N log N)`. Сам запрос на поиск минимума на произвольном отрезке `[L, R]` выполняется за константное время `O(1)` путем нахождения минимума между двумя перекрывающимися отрезками степени двойки.
Топологическая сортировка упорядочивает вершины ориентированного ациклического графа (DAG) так, чтобы для любого ребра `(U, V)` вершина `U` шла до `V` (например, планирование задач с зависимостями). **Реализация через DFS**: 1. Запускается DFS для всех непосещенных вершин. 2. При выходе из рекурсивного обхода вершины (когда все ее соседи уже обойдены), вершина добавляется в начало результирующего списка. 3. Если в процессе DFS обнаруживается ребро, ведущее в серую вершину (уже обрабатываемую в стеке рекурсии), в графе есть цикл, и топологическая сортировка невозможна.
Битовая маска — это представление подмножества элементов с помощью целого числа, где каждый бит указывает на наличие (`1`) или отсутствие (`0`) элемента в подмножестве. * **Операции**: Добавление элемента: `mask | (1 << i)`. Проверка наличия: `(mask & (1 << i)) != 0`. Удаление: `mask & ~(1 << i)`. * **Применение**: Задачи динамического программирования по профилю/подмножествам (например, задача коммивояжера при малом N), где нужно перебрать все возможные состояния системы.
DSU (Disjoint Set Union) хранит семейство непересекающихся множеств и поддерживает две операции: * `Union(A, B)`: Объединить два множества в одно. * `Find(A)`: Найти представителя (лидера) множества, в котором находится элемент A. **Оптимизации**: 1. **Эвристика сжатия путей (Path Compression)**: При поиске `Find` все узлы на пути перенаправляются напрямую на лидера, что делает последующие поиски мгновенными. 2. **Ранговая эвристика**: При объединении дерево меньшей высоты подвешивается к большему. Сложность операций становится почти константной: `O(α(N))`, где α — обратная функция Аккермана.
Алгоритм Косарайю находит сильно связные компоненты (SCC) в ориентированном графе за два прохода DFS: 1. Запускается DFS на исходном графе. Вершины записываются в стек по мере завершения их обработки (аналогично топологической сортировке). 2. Строится транспонированный граф (все ребра разворачиваются в обратном направлении). 3. Вершины извлекаются из стека. Для каждой непосещенной вершины запускается DFS на транспонированном графе. Все достигнутые вершины образуют один сильно связный компонент.