Сложность: O(1), O(n), O(n log n)
Две функции могут давать один и тот же ответ, но на большом векторе одна работает доли секунды, а другая — часы. Разницу видно, если посчитать шаги. Функция count_steps выполняет ++steps для каждой пары i и j:
#include <iostream>
int count_steps(int n) {
int steps = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
++steps;
}
}
return steps;
}
int main() {
std::cout << count_steps(10) << ' ' << count_steps(1000) << '\n'; // 100 1000000
}Входные данные выросли в сто раз, а число шагов — в десять тысяч раз.
Запись O(…)
Сложность алгоритма (time complexity) показывает, как число шагов растёт вместе с размером входных данных n. Её записывают в O-нотации (Big-O notation): count_steps делает n² шагов, и её сложность — O(n²). Постоянные множители и меньшие слагаемые отбрасывают: 3n + 5 шагов — это O(n), а n²/2 шагов — O(n²). При больших n они почти не меняют картину роста.
Обычно сложность указывают для худшего случая (worst case) — входа, на котором алгоритм делает больше всего шагов. Поиск, который останавливается на найденном элементе, в худшем случае ничего не находит и проверяет все n элементов. Поэтому его сложность — O(n), хотя иногда он заканчивается на первом шаге.
| Сложность | Пример | При n = 10⁶ |
|---|---|---|
| O(1) | v[i], v.size() | 1 |
| O(log n) | поиск ключа в std::map | ≈ 20 |
| O(n) | один цикл по вектору | 10⁶ |
| O(n log n) | цикл, который ищет в std::map | ≈ 2 · 10⁷ |
| O(n²) | два вложенных цикла по вектору | 10¹² |
Оценка по коду
Один цикл по n элементам — это O(n). Вложенные циклы перемножают числа шагов: n раз по n — O(n²). Циклы, которые идут друг за другом, складываются, и остаётся больший: O(n) + O(n²) — это O(n²).
Внутренний цикл часто начинают с i + 1, чтобы не сравнивать одну пару дважды. Он становится короче, но всего выполняется n(n−1)/2 раз, и сложность остаётся O(n²). Если цикл на каждом шаге ищет ключ в std::map, сложности перемножаются: n раз по log n — O(n log n). Цикл, который на каждом шаге делит n пополам, делает около log₂ n шагов — это O(log n).
Частая ошибка
Элементы вектора обрабатывают по одному, каждый раз удаляя первый:
std::vector<int> v{3, 1, 2};
while (!v.empty()) {
std::cout << v[0] << ' ';
v.erase(v.begin()); // ✗
}Программа выводит верный результат, но на большом векторе работает медленно. Цикл выглядит как O(n), однако erase сдвигает все оставшиеся элементы на одно место влево. Для n элементов это n − 1, n − 2, … сдвигов, всего O(n²). Обойдите вектор циклом по диапазону: это O(n), и удалять ничего не нужно.
