Когда говорят про «сложность программы», имеют в виду сложность в модели RAM (Random Access Machine). Суть модели:
Тогда цикл, который проходит по массиву длины $n$ и читает каждый элемент, делает $O(n)$ операций.
2:27 Цель всей оценки: по размерам входных данных понять, сколько действий сделает программа, то есть узнать, «зайдёт» ли решение по времени, ещё до запуска.
Запись «программа работает за $O(n)$» не означает, что она делает ровно $n$ действий.
То есть существует константа $C$, такая что если умножить $n$ на $C$, то реальное число действий программы при любом (достаточно большом) $n$ будет не больше этой величины.
$O(1)$. Программа, которая читает два числа $a$ и $b$ и выводит их сумму:
int a, b;
cin >> a >> b;
cout << a + b;Независимо от входных данных она делает какое-то константное количество действий (например, не больше 100). Это $O(1)$: есть константа (например, $100$), которую можно умножить на $1$, чтобы она накрыла число действий программы.
$O(n)$. Программа вводит число $n$, потом $n$ чисел и выводит их:
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < n; ++i) cout << a[i] << " ";Здесь два цикла по $n$, плюс немного операций «единичного» порядка. Итог: $n \cdot (\text{константа}) + (\text{константа}) = O(n)$.
$O(n^2)$. Пусть есть два массива $a$ и $b$ длины $n$ каждый, нужно посчитать сумму $a_i \cdot b_j$ по всем парам $(i,j)$:
long long s = 0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
s += a[i] * b[j];Внешний цикл $n$ раз, и на каждой итерации внутренний цикл делает $n$ действий. Итого $n \cdot n = O(n^2)$.
В предыдущем примере программа разбивается на три куска: $O(1)$ (ввод $n$), $O(n)$ (ввод массивов) и $O(n^2)$ (двойной цикл). Итоговая сложность — $n^2 + n + 1$.
Но по определению мы можем взять $C = c + 1$ и увидеть, что
Суть: мы «вырезали» слагаемое $n^2$ и добавили ещё одно $n^2$; а $n^2 > n + 1$ при больших $n$.
Важный приём, который будет встречаться часто: два вложенных цикла не всегда дают $n^2$. Рассмотрим идею на примере.
for i = 0..n:
S += a[i] * a[j] // j — ОБЩИЙ указатель, объявленный вне цикла
while j < n and a[j] < a[i]:
j += 1С первого взгляда кажется, что это $O(n^2)$: внешний цикл до $n$, внутренний while до $n$. Но это не так. Ключевое наблюдение:
while выполнится не больше $n$ раз.Интуиция через «монетки» 21:06: представьте, что у вас $2n$ монеток, и вы платите монетку каждый раз, когда заходите внутрь циклов. За каждый $i$ вы платите монетку, и за каждый $j$ платите монетку. $i$ растёт до $n$ (это $n$ монеток), $j$ суммарно растёт до $n$ (ещё $n$ монеток). Всего вы потратите не больше $2n$ монеток.
for j = 0..n внутри — это был бы честный $O(n^2)$.Оценка сложности нужна не ради оценки, а чтобы понять, «зайдёт ли решение». Есть простой лайфхак:
Это грубая оценка: деление дороже сложения, но порядок величины такой. Что отсюда следует:
| Ограничение на $n$ | Сложность, которая точно зайдёт | Комментарий |
|---|---|---|
| $n \le 10^5$ | $O(n)$ | миллисекунды, огромный запас |
| $n \le 10^4$ | $O(n^2)$ | $\approx 10^8$, около секунды |
| $n \le 10^3$ | $O(n^2)$ | $10^6$, запас ~200× |
| $n \le 500$ | $O(n^3)$ | $1.25\cdot 10^8$, на грани |
| $n \le 100$ | $O(n^3)$ | $10^6$, заходит с запасом |
Два решения с одной и той же асимптотикой могут работать совершенно по-разному, потому что в $O$-нотации «спрятана» константа.
Пример: цикл, который делает фиксированные $1000$ действий, и цикл, который делает $1$ действие, — оба $O(1)$, но первый в $1000$ раз дольше. Асимптотически они одинаковы, но «разумность» константы никто не отменял.
// Вариант 1: внутри цикла по n — фиксированные 10000 действий
for i = 0..n:
x += 10000 // 10^4 действий на каждую из n итераций
// Вариант 2: два честных цикла по n
for i = 0..n: x += a[i]
for i = 0..n: y += a[i]Оба варианта работают за $O(n)$. Но пусть $n = 10^6$:
Квадратичные сортировки — это сортировки, работающие за $O(n^2)$ времени от размера массива $n$. Разбираем три: пузырёк, выбором, вставками.
Идея. Идём слева направо и смотрим на пары соседних элементов. Если левый больше правого — меняем их местами. Так проходим весь массив.
Интерактив: двигайте ползунок или нажмите ▶ — сравниваемая пара жёлтая, обмен красный, отсортированный хвост зелёный.
Ключевой факт. После первого прохода максимальный элемент стоит на своём месте — в конце массива. Почему? Когда мы доходим до максимума, он больше всех, кто стоит справа от него, поэтому на каждом следующем шаге меняется с соседом и «проплывает» в самый конец.
Тогда на втором проходе то же самое верно для массива без последнего элемента — второй по величине элемент встанет на предпоследнее место. И так далее: на $i$-м проходе $i$-й по убыванию элемент встаёт на своё место.
// bubble sort
for (int i = 0; i < n - 1; ++i) { // номер прохода
for (int j = 0; j < n - 1 - i; ++j) { // проход слева направо
if (a[j] > a[j + 1]) { // соседи в неправильном порядке
swap(a[j], a[j + 1]); // меняем
}
}
}Идея. На первое место надо поставить минимальный элемент всего массива. Проходим по всему массиву, находим минимум, ставим его на место. Дальше на оставшемся суффиксе снова ищем минимум и ставим на второе место, и так далее.
Интерактив: ползунок/▶ — ищем минимум суффикса (жёлтая пара), ставим его в начало (красный обмен), отсортированный префикс зелёный.
Сложность. Проходов $O(n)$; на каждом ищем минимум на всё уменьшающемся суффиксе: $n$, затем $n-1$, затем $n-2$, … Сумма:
// selection sort
for (int i = 0; i < n; ++i) { // с какого индекса начинается суффикс
int pos = i; // позиция текущего минимума
for (int j = i + 1; j < n; ++j) { // ищем минимум на суффиксе [i..n)
if (a[j] < a[pos]) pos = j;
}
swap(a[i], a[pos]); // ставим минимум на место i
}Идея и инвариант. Введём понятие инварианта — свойства, которое не меняется на протяжении всего алгоритма.
База: префикс длины $1$ (один элемент) отсортирован. Переход: если префикс длины $i$ отсортирован, то единственное, что может «мешать» префиксу длины $i+1$ быть отсортированным, — последний (новый) элемент. Вставим его на своё место — и весь префикс длины $i+1$ станет отсортирован.
Чтобы «вставить», не обязательно использовать явную функцию вставки: достаточно менять элемент с предыдущим, пока он не встанет на своё место (пока предыдущий не станет $\le$ текущего).
// insertion sort
for (int i = 1; i < n; ++i) { // первый элемент уже «на месте»
int j = i;
while (j > 0 && a[j] < a[j - 1]) {
swap(a[j], a[j - 1]);
--j;
}
}Интерактив: ползунок/▶ — новый элемент вставляется на место, сдвигая большие вправо (красные обмены).
Сложность. $n$ элементов, вставка каждого в худшем случае $O(n)$ ⇒ $O(n^2)$.
Идея. Пусть все числа в массиве неотрицательные и не очень большие: $a_i \le k$ (например, $k \le 10^5$). Заведём массив cnt размера $k+1$, где будем подсчитывать, сколько раз встретилось каждое число. Потом пройдёмся по cnt и выведем каждое число столько раз, сколько оно встретилось.
Интерактив: ползунок/▶ — сначала считаем частоты (cnt), затем выводим значения по возрастанию.
Сложность. Нужно пройти по исходному массиву длины $n$ и в конце по массиву cnt размера $k+1$:
Если $k$ маленькое (например, $k \le 100$), алгоритм эффективен — работает за линейное от $n$ время, быстрее обычной сортировки. Вывод: если знаете, что различных значений немного и все они небольшие, — используйте подсчёт.
Если же элементы могут быть произвольными (например, до $10^{18}$), сортировка подсчётом невыгодна (массив cnt такого размера не создать).
// counting sort: числа от 0 до k включительно
vector<int> cnt(k + 1, 0);
for (int x : a) cnt[x]++; // подсчёт
for (int i = 0; i <= k; ++i)
for (int t = 0; t < cnt[i]; ++t)
cout << i << " "; // выводим i ровно cnt[i] разПодзадача. Есть два уже отсортированных массива $a$ и $b$ (возможно, разной длины). Нужно получить из них один отсортированный массив.
Тривиально можно склеить их и вызвать сортировку, но это даст $O(n\log n)$ (или $O(n^2)$ квадратичной). Но эту задачу можно решить за линейное время $O(|a| + |b|)$.
Идея (два указателя). Кто может быть первым (минимальным) элементом результата? Либо первый элемент $a$, либо первый элемент $b$: всё, что правее первого элемента массива, не меньше его. Сравниваем их, меньший выписываем, двигаем соответствующий указатель вправо. Повторяем. Когда один массив закончится — дописываем остаток другого.
Интерактив: ползунок/▶ — два указателя (a зелёный, b оранжевый) по очереди выписывают меньший элемент.
// слить два отсортированных вектора в один
vector<int> merge(const vector<int>& a, const vector<int>& b) {
vector<int> res;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] <= b[j]) res.push_back(a[i++]);
else res.push_back(b[j++]);
}
// один из массивов уже закончился — дописываем остаток второго
while (i < a.size()) res.push_back(a[i++]);
while (j < b.size()) res.push_back(b[j++]);
return res;
}Каждый элемент $a$ и каждый элемент $b$ обрабатывается ровно один раз, поэтому сложность — линейная от суммарной длины.
Теперь решим исходную задачу — отсортировать произвольный массив.
merge в один отсортированный массив.База рекурсии: массив из одного элемента уже отсортирован.
Обозначим уровни рекурсии: нулевой — весь массив, первый — две половинки, второй — четвертинки, и так далее.
Сколько уровней? Это число раз, которое можно поделить $n$ на $2$, пока не останется $1$. У этого числа есть название:
Логарифм растёт очень медленно. Вот конкретные значения:
| $n$ | $\log_2 n$ (примерно) |
|---|---|
| $10^5$ | $\approx 16$ |
| $10^6$ | $\approx 20$ |
| $10^9$ | $\approx 30$ |
Это значит, что $n \log n$ очень близко к линейному времени: $n$ умножается на совсем маленькое число. Для $n = 10^5$ это $\approx 1.6 \cdot 10^6$ — быстрое решение. Если бы было $n^2$, $n$ умножилось бы на $10^5$ — это очень много.
std::sort 1:31:20Если нужно просто отсортировать массив, руками писать сортировку не надо — в C++ есть встроенная:
#include <algorithm>
sort(a.begin(), a.end()); // отсортирует вектор по неубываниюПосле перерыва разбирался вводный контест по C++ (4 задачи).
Простейшая задача: объявить переменные, ввести их и вывести сумму.
int a, b;
cin >> a >> b;
cout << a + b;(a + b - 1) / b.В некоторых задачах нужно читать из файла и писать в файл (а не в стандартный ввод/вывод). Названия файлов указаны в условии (например, divide.in и divide.out).
#include <cstdio>
int main() {
freopen("divide.in", "r", stdin); // читаем из divide.in
freopen("divide.out", "w", stdout); // пишем в divide.out
int a, b; cin >> a >> b;
cout << a / b;
return 0;
}"r" — от слова read (читать), "w" — от write (писать).stdin читается из файла, а stdout пишется в файл.Нужно вводить числа, пока не встретится $0$ (признак конца), и вывести их в обратном порядке.
#include <vector>
#include <algorithm>
vector<int> a;
int x;
while (cin >> x && x != 0) { // ноль — признак конца, в массив его не кладём
a.push_back(x);
}
reverse(a.begin(), a.end()); // развернуть вектор (лежит в <algorithm>)
for (int v : a) cout << v << " ";reverse из <algorithm> разворачивает вектор задом наперёд.for (int v : a) — range-based for, краткая запись перебора всех элементов вектора от начала до конца (без индексов).Напоминает сортировку подсчётом: заводим массив счётчиков на 26 букв.
#include <string>
#include <vector>
vector<int> cnt(26, 0); // 26 букв, изначально нули
string s; cin >> s;
for (char x : s)
cnt[x - 'a']++; // 'a' → 0, 'b' → 1, ..., 'z' → 25
for (int i = 0; i < 26; ++i)
cout << cnt[i] << " ";Как работает x - 'a':
char сопоставлено число по таблице ASCII (общепринятый стандарт хранения символов в памяти).'a' = 97, 'b' = 98, 'c' = 99, …x - 'a' даёт номер буквы от $0$ до $25$ — индекс в массиве cnt..cpp-файл и добавляют его в CMakeLists.txt (копируют строку про add_executable и меняют имя). После этого в списке запуска появляется второй вариант, который можно запускать независимо.