Алгоритмы

Как оценивать и выбирать алгоритмы — сложность, сортировка, поиск, рекурсия, графы, динамическое программирование, структуры данных и алгоритмы STL.

IT Abyss

Алгоритмы — как выбрать, а не вспомнить

Алгоритм — это не заклинание, которое надо вспомнить на собеседовании. Это решение, которое вы принимаете каждый день: взять std::map или std::unordered_map, написать рекурсию или цикл, отсортировать заранее или искать линейно. Цена ошибки в этом выборе не теоретическая — она измеряется в миллисекундах задержки и мегабайтах памяти.

В C++ выбор алгоритма особенно нагляден, потому что язык не прячет цену. Вы видите, как рекурсия растит стек, как лишняя аллокация бьёт по кэшу, как O(n²) на отсортированном входе превращает быстрый код в зависший. Поэтому уметь алгоритмы — значит не помнить псевдокод, а понимать стоимость каждого варианта и осознанно выбирать.

Сложность алгоритмов

Сложность (Big-O) описывает, как растут время или память с ростом размера входа n. Это скорость роста, а не абсолютная скорость: O(n) с большой константой может на малых n проигрывать O(n²).

Различают три оценки: худший случай (O), средний (Θ) и лучший (Ω). На собеседовании по умолчанию спрашивают худший случай. Основные классы по возрастанию:

O(1) — константа: доступ по индексу, вставка в хеш-таблицу (в среднем).
O(log n) — бинарный поиск, высота сбалансированного дерева.
O(n) — линейный проход.
O(n log n) — нижняя граница для сортировки сравнениями.
O(n²) — вложенные циклы по входу.
O(2ⁿ) — полный перебор, наивная рекурсия Фибоначчи.

Не забывайте про пространственную сложность: рекурсивный алгоритм часто экономит время ценой стека вызовов. И операции хеш-таблицы — O(1) лишь в среднем; в худшем случае коллизии дают O(n).

Рекурсия

Рекурсия — это функция, вызывающая саму себя. Каждый вызов кладёт на стек новый кадр, поэтому у рекурсии обязан быть базовый случай — условие остановки. Без него или при слишком глубокой рекурсии стек переполняется.

// Наивная рекурсия Фибоначчи: O(2ⁿ) — fib(40) уже считается секунды
long long fib_slow(int n) {
    if (n < 2) return n;                  // базовый случай
    return fib_slow(n - 1) + fib_slow(n - 2);
}

// Мемоизация: каждый fib(k) считается один раз → O(n)
long long fib_memo(int n, std::vector<long long>& cache) {
    if (n < 2) return n;
    if (cache[n] != -1) return cache[n];   // готовый ответ
    return cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
}

Рекурсия против итерации — это размен. Рекурсия короче и яснее для деревьев и «разделяй и властвуй»; итерация не растит стек и предсказуема по памяти. Мемоизация превращает экспоненциальную рекурсию в линейную, кэшируя результаты подзадач — наивный fib(40) считается секунды, мемоизированный мгновенен.

Сортировка и поиск

Сортировка сравнениями не может быть быстрее O(n log n) — это доказанная нижняя граница. Три алгоритма, которые надо знать:

Quicksort — на месте, в среднем O(n log n), но при плохом выборе опорного элемента (например, всегда первый) на отсортированном входе деградирует до O(n²).
Merge sort — стабильна, гарантированные O(n log n), но требует O(n) дополнительной памяти.
Introsort — то, что внутри std::sort: quicksort, который при слишком глубокой рекурсии переключается на heapsort, а на маленьких подмассивах — на сортировку вставками.

Стабильность означает, что элементы с равными ключами сохраняют исходный относительный порядок. Это важно при сортировке по вторичному ключу: std::stable_sort стабильна (ценой O(n) памяти), std::sort — нет.

Бинарный поиск работает за O(log n), но только на отсортированных данных.

int binary_search(const std::vector<int>& v, int target) {
    int low = 0, high = (int)v.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // не (low+high)/2 — переполнение
        if (v[mid] == target) return mid;
        if (v[mid] < target) low = mid + 1;
        else                 high = mid - 1;
    }
    return -1;
}

Две классические ловушки: mid = (low + high) / 2 переполняется при больших индексах — пишите low + (high - low) / 2; и граница цикла while (low <= high) против < high меняет семантику — ошибка на единицу здесь даёт неверный результат.

Структуры данных

Связный список — это узлы, связанные указателями. Вставка и удаление в известной позиции — O(1), но доступ по индексу — O(n). При развороте списка главное — сохранить указатель на следующий узел до того, как перезапишете next:

Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* next = head->next;   // сохранить ДО перезаписи
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;                   // вернуть prev, не head — head уже nullptr
}

Деревья. Двоичное дерево поиска (BST) держит инвариант: слева — меньшие значения, справа — большие. Поиск — O(log n) на сбалансированном дереве и O(n) на вырожденном (BST гарантирует порядок значений, но не балансировку). Обходы: pre-order, in-order, post-order и level-order; in-order обход BST выдаёт значения в отсортированном порядке.

Хеш-таблица отображает ключ в корзину через хеш-функцию: поиск в среднем O(1), в худшем O(n) при кластеризации. При превышении коэффициента заполнения таблица перехеширует данные в больший массив.

Стек (LIFO) и очередь (FIFO) — простейшие структуры. Очередь фиксированного размера удобно реализовать кольцевым буфером; там главная ловушка — различить «пусто» и «полно» (отдельный счётчик размера или жертва одной ячейки).

Графовые алгоритмы

Граф — это вершины и рёбра; в памяти его представляют списком смежности (компактно для разреженных графов) или матрицей. Два базовых обхода:

BFS (поиск в ширину) использует очередь, идёт по уровням и находит кратчайший путь в невзвешенном графе.
DFS (поиск в глубину) использует стек или рекурсию, уходит вглубь — основа топологической сортировки и анализа достижимости.

В любом обходе обязательно помечайте посещённые вершины — иначе на циклическом графе обход зациклится.

Алгоритм Дейкстры ищет кратчайшие пути во взвешенном графе с неотрицательными рёбрами; эффективным его делает приоритетная очередь. На графе с отрицательными рёбрами Дейкстра даёт неверный результат — там нужен Беллман-Форд.

Обнаружение цикла зависит от типа графа: в ориентированном — DFS с тремя цветами вершин (обратное ребро ведёт в «серую» вершину на текущем пути); в неориентированном — система непересекающихся множеств (union-find).

Динамическое программирование

Динамическое программирование (DP) применимо, когда задача распадается на перекрывающиеся подзадачи и обладает оптимальной подструктурой. Два стиля:

Мемоизация (сверху вниз) — обычная рекурсия плюс кэш уже посчитанных подзадач.
Табуляция (снизу вверх) — итеративное заполнение таблицы от базовых случаев к ответу.

Когда рекуррента опирается только на последнюю строку таблицы, память сворачивают с O(n²) до O(n). И кэш мемоизации лучше держать в массиве, а не в std::map — O(1) против O(log n) на обращение.

Строковые алгоритмы

Поиск подстроки наивно стоит O(n·m); алгоритм Кнута — Морриса — Пратта (KMP) делает это за O(n + m), переиспользуя информацию о уже совпавшем префиксе. Вызывать std::string::find в цикле — типичный способ случайно получить O(n²).

Проверку палиндрома не нужно делать через разворот строки с лишней O(n) памятью — достаточно двух указателей навстречу друг другу. И помните: сравнение строк в C++ — это O(n), а не O(1) как сравнение указателей. С не-ASCII текстом работайте по кодовым точкам, а не по байтам.

Битовые операции

Битовые операции (&, |, ^, сдвиги) — компактный и быстрый инструмент. Несколько приёмов, которые любят на собеседованиях:

// Подсчёт установленных битов — трюк Кернигана: O(числа битов), не O(32)
int count_bits(unsigned n) {
    int count = 0;
    while (n) { n &= (n - 1); ++count; }   // n & (n-1) гасит младший единичный бит
    return count;
}

n & (n - 1) сбрасывает младший установленный бит — отсюда подсчёт за число единиц, а не за разрядность. В C++20 это и вовсе однострочник std::popcount. Ещё один классический приём — XOR: если в массиве все элементы парные, кроме одного, XOR всех элементов даёт уникальный за O(1) памяти. Для битовых операций берите беззнаковые типы — у знаковых сдвиг и переполнение ведут к UB.

Алгоритмы STL

Стандартная библиотека даёт <algorithm> — std::sort, std::find, std::transform, std::accumulate и десятки других. Их преимущество над ручным циклом: они корректны, оптимизированы и выразительны — намерение читается с первого взгляда.

Главные ловушки:

Идиома erase-remove. std::remove и std::remove_if физически не уменьшают контейнер — они лишь сдвигают «выжившие» элементы и возвращают новый конец; реально удаляет элементы последующий erase. В C++20 чище — std::erase_if.
Требования к итераторам. std::sort нужен произвольный доступ — на std::list он не скомпилируется, у списка свой метод list::sort(). std::binary_search, lower_bound, upper_bound требуют отсортированный диапазон.
Execution policy (C++17). Передав std::execution::par, вы просите распараллелить алгоритм. Но par не делает код потокобезопасным сам по себе — общее состояние всё равно нужно защищать; и на маленьком входе накладные расходы на потоки съедают выигрыш.

Частые ошибки и ловушки

Ошибка	Последствие
Big-O принимают за абсолютную скорость	На малых `n` `O(n)` с большой константой проигрывает `O(n²)`
Хеш-операции считают всегда `O(1)`	В худшем случае коллизии дают `O(n)`
Рекурсия без базового случая или слишком глубокая	Переполнение стека
Наивная рекурсия там, где нужна мемоизация	Экспоненциальное время вместо линейного
`mid = (low + high) / 2` в бинарном поиске	Переполнение при больших индексах
Бинарный поиск по неотсортированным данным	Неверный результат
Quicksort с первым элементом как опорным	`O(n²)` на уже отсортированном входе
При развороте списка `next` не сохранён до перезаписи	Потеря хвоста списка
Обход графа без отметки посещённых вершин	Зацикливание на циклическом графе
Дейкстра на графе с отрицательными рёбрами	Неверные кратчайшие пути — нужен Беллман-Форд
`std::remove` без последующего `erase`	Контейнер не уменьшился — «удалённые» элементы остались
`std::execution::par` без защиты общего состояния	Гонка данных

Значение для собеседований

Алгоритмы — ядро технического собеседования на любую C++-позицию. Но проверяют не умение вспомнить псевдокод, а инженерное суждение: умеете ли вы оценить сложность, выбрать структуру данных и заметить ловушку.

Что проверяет интервьюер:

Оценку сложности по времени и памяти, разницу худшего и среднего случая
Рекурсию против итерации и роль мемоизации
Выбор сортировки: quicksort, merge sort, introsort — и что значит стабильность
Корректный бинарный поиск без переполнения и ошибки на единицу
Структуры данных: связные списки, деревья, хеш-таблицы — их сложности
Графовые обходы (BFS vs DFS) и границы применимости Дейкстры
Знание <algorithm>: идиому erase-remove, требования к итераторам

Типичные вопросы:

Что такое сложность Big-O и как её определить?
В чём разница мемоизации и табуляции?
Сравните quicksort и merge sort по сложности, стабильности и памяти.
Когда выбрать BFS, а когда DFS?
Как работает Дейкстра и почему он ломается на отрицательных рёбрах?
Зачем нужна идиома erase-remove?

Типичная ошибка: писать код, не оценив его сложность и не назвав граничные случаи (пустой вход, один элемент, переполнение). Интервьюер ищет того, кто выбирает алгоритм осознанно и видит ловушки заранее, а не вспоминает заученное решение.

beginner

Algorithms

How to evaluate and choose algorithms — complexity, sorting, searching, recursion, graphs, dynamic programming, data structures, and STL algorithms.

Algorithms

Practice: 42 questions · 25 tasks →

Contents

Detailed explanation

Algorithms—Choose wisely, don't just recall

An algorithm is not a magic spell to recite at an interview. It is a decision you make every day: use std::map or std::unordered_map, write recursion or a loop, sort beforehand or search linearly. The cost of a wrong choice is not theoretical—it is measured in milliseconds of latency and megabytes of memory.

In C++ the choice of algorithm is especially visible, because the language does not hide the cost. You see recursion growing the stack, you see an extra allocation miss the cache, you see O(n²) on sorted input turn fast code into a hang. To understand algorithms means not to memorize pseudocode, but to grasp the cost of each choice and decide consciously.

Complexity analysis

Complexity (Big-O) describes how runtime or memory grows as the input size n grows. It is a growth rate, not absolute speed: O(n) with a large constant can lose to O(n²) on small inputs.

Three estimates exist: worst case (O), average case (Θ), and best case (Ω). In an interview, worst case is the default unless stated otherwise. The main classes in order of growth:

O(1) — constant: array index access, hash table insertion (average case).
O(log n) — binary search, height of a balanced tree.
O(n) — linear scan.
O(n log n) — lower bound for comparison-based sorting.
O(n²) — nested loops over the input.
O(2ⁿ) — full enumeration, naive Fibonacci recursion.

Don't forget space complexity: recursive algorithms often trade time for stack depth. And hash table operations are O(1) only on average; in the worst case, collisions give O(n).

Recursion

Recursion is a function calling itself. Each call pushes a new frame onto the call stack, so recursion must have a base case—a stopping condition. Without it, or with recursion too deep, the stack overflows.

// Naive Fibonacci recursion: O(2ⁿ) — fib(40) takes seconds
long long fib_slow(int n) {
    if (n < 2) return n;                  // base case
    return fib_slow(n - 1) + fib_slow(n - 2);
}

// Memoization: each fib(k) computed once → O(n)
long long fib_memo(int n, std::vector<long long>& cache) {
    if (n < 2) return n;
    if (cache[n] != -1) return cache[n];   // cached answer
    return cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
}

Recursion vs. iteration is a tradeoff. Recursion is shorter and clearer for trees and divide-and-conquer; iteration does not grow the stack and is predictable in memory. Memoization turns exponential recursion into linear by caching subproblem results—naive fib(40) takes seconds, memoized is instant.

Sorting and searching

Comparison-based sorting cannot be faster than O(n log n)—this is a proven lower bound. Three algorithms to know:

Quicksort — in-place, average O(n log n), but with a poor pivot choice (e.g., always the first element) it degrades to O(n²) on sorted input.
Merge sort — stable, guaranteed O(n log n), but needs O(n) extra space.
Introsort — what std::sort uses: quicksort that switches to heapsort if recursion gets too deep, and insertion sort on small subarrays.

Stability means elements with equal keys preserve their original relative order. This matters when sorting by a secondary key: std::stable_sort is stable (at the cost of O(n) memory), std::sort is not.

Binary search runs in O(log n), but only on sorted data.

int binary_search(const std::vector<int>& v, int target) {
    int low = 0, high = (int)v.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;   // not (low+high)/2 — overflow
        if (v[mid] == target) return mid;
        if (v[mid] < target) low = mid + 1;
        else                 high = mid - 1;
    }
    return -1;
}

Two classic traps: mid = (low + high) / 2 overflows on large indices—write low + (high - low) / 2 instead; and the loop bound while (low <= high) vs. < high changes semantics—an off-by-one error here gives a wrong result.

Data structures

Linked list — nodes connected by pointers. Insertion and removal at a known position is O(1), but random access is O(n). When reversing a list, save the next pointer before overwriting next:

Node* reverse(Node* head) {
    Node* prev = nullptr;
    while (head) {
        Node* next = head->next;   // save BEFORE overwrite
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;                   // return prev, not head — head is nullptr now
}

Trees. A binary search tree (BST) maintains an invariant: smaller values to the left, larger to the right. Search is O(log n) on a balanced tree and O(n) on a degenerate one (BST guarantees value order but not balance). Traversals: pre-order, in-order, post-order, and level-order; in-order traversal of a BST yields values in sorted order.

Hash table maps a key to a bucket via a hash function: average-case search is O(1), worst case is O(n) on collisions. When the load factor is exceeded, the table rehashes into a larger array.

Stack (LIFO) and queue (FIFO)—the simplest data structures. A fixed-size queue is cleanly implemented as a circular buffer; the main trap there is distinguishing empty from full (a separate size counter or sacrifice one cell).

Graph algorithms

A graph is vertices and edges; in memory it is represented as an adjacency list (compact for sparse graphs) or a matrix. Two basic traversals:

BFS (breadth-first search) uses a queue, explores level-by-level, and finds the shortest path in an unweighted graph.
DFS (depth-first search) uses a stack or recursion, goes deep—the foundation of topological sorting and reachability analysis.

In any traversal, mark visited vertices—otherwise, a cyclic graph will loop forever.

Dijkstra's algorithm finds shortest paths in a weighted graph with non-negative edges; a priority queue makes it efficient. On graphs with negative edges, Dijkstra gives wrong results—use Bellman-Ford instead.

Cycle detection depends on the graph type: in directed graphs, DFS with three-color marking (a back edge reaches a "gray" vertex on the current path); in undirected graphs, a union-find (disjoint-set) structure.

Dynamic programming

Dynamic programming (DP) applies when a problem decomposes into overlapping subproblems and has optimal substructure. Two styles:

Memoization (top-down)—normal recursion plus a cache of solved subproblems.
Tabulation (bottom-up)—iteratively fill a table from base cases to the answer.

When the recurrence only depends on the last row of the table, memory can be compressed from O(n²) to O(n). And a memoization cache is better kept in an array than std::map—O(1) vs. O(log n) per lookup.

String algorithms

Naive substring search is O(n·m); the Knuth-Morris-Pratt (KMP) algorithm does it in O(n + m) by reusing information about the prefix already matched. Calling std::string::find in a loop is a classic way to accidentally get O(n²).

Palindrome checking does not need to reverse the string and waste O(n) space—use two pointers moving toward each other. And remember: string comparison in C++ is O(n), not O(1) like pointer comparison. Work with non-ASCII text by Unicode code points, not bytes.

Bitwise operations

Bitwise operations (&, |, ^, shifts)—compact and fast. A few tricks beloved by interviewers:

// Count set bits — Kernighan's trick: O(number of bits), not O(32)
int count_bits(unsigned n) {
    int count = 0;
    while (n) { n &= (n - 1); ++count; }   // n & (n-1) clears the lowest set bit
    return count;
}

n & (n - 1) clears the lowest set bit—hence the count runs in the number of set bits, not word width. In C++20 this is a one-liner: std::popcount. Another classic—XOR: if all array elements appear twice except one, XOR all of them to get the unique element in O(1) space. For bitwise work, use unsigned types—signed types have undefined behavior on shift and overflow.

STL algorithms

The standard library provides <algorithm>—std::sort, std::find, std::transform, std::accumulate, and dozens more. Their advantage over manual loops: correctness, optimization, and clarity—intent reads at a glance.

Key pitfalls:

Erase-remove idiom. std::remove and std::remove_if do not physically shrink the container—they shift "survivors" and return a new end; erase actually removes. In C++20, std::erase_if is cleaner.
Iterator requirements. std::sort needs random access—it won't compile on std::list, which has its own list::sort() method. std::binary_search, lower_bound, upper_bound require a sorted range.
Execution policy (C++17). Passing std::execution::par asks the algorithm to parallelize. But par does not make code thread-safe by itself—shared state still needs protection; and on small inputs the thread overhead eats the speedup.

Common traps and mistakes

Mistake	Consequence
Treating Big-O as absolute speed	On small `n`, `O(n)` with a large constant loses to `O(n²)`
Assuming hash operations are always `O(1)`	Collisions give `O(n)` worst case
Recursion without a base case or too deep	Stack overflow
Naive recursion where memoization is needed	Exponential time instead of linear
`mid = (low + high) / 2` in binary search	Overflow on large indices
Binary search on unsorted data	Wrong result
Quicksort with first element as pivot	`O(n²)` on already-sorted input
Forgetting to save `next` before overwriting in list reversal	Loss of tail
Graph traversal without marking visited vertices	Infinite loop on cyclic graphs
Dijkstra on a graph with negative edges	Wrong shortest paths—need Bellman-Ford
`std::remove` without following `erase`	Container unchanged—"removed" elements stay
`std::execution::par` without protecting shared state	Data race

Relevance for interviews

Algorithms are the core of technical interviews at any C++ level. But the interviewer is not checking memorized pseudocode—they are checking engineering judgment: can you estimate complexity, choose a data structure, and spot a trap?

What the interviewer checks:

Time and space complexity estimation, difference between worst and average case
Recursion vs. iteration, and the role of memoization
Sorting choices: quicksort, merge sort, introsort—and what stability means
Correct binary search without overflow or off-by-one errors
Data structures: linked lists, trees, hash tables—their complexities
Graph traversals (BFS vs. DFS) and limits of Dijkstra
Knowledge of <algorithm>: erase-remove idiom, iterator requirements

Typical questions:

What is Big-O complexity and how do you determine it?
What is the difference between memoization and tabulation?
Compare quicksort and merge sort by complexity, stability, and memory.
When do you choose BFS over DFS?
How does Dijkstra work, and why does it break on negative edges?
Why does the erase-remove idiom exist?

Common mistake: writing code without estimating its complexity or naming edge cases (empty input, single element, overflow). The interviewer is looking for someone who picks an algorithm consciously and sees traps beforehand—not someone who recites a memorized solution.

Why it matters

An algorithm is not something to recall at an interview—it is something to choose wisely. The difference between O(n) and O(n²), between recursion and iteration, between quicksort and merge sort—this is not theory, it is the cost paid in milliseconds and megabytes every single day.