Учебник по информатике и математике
Темы
C++
Основы языка
Сложность алгоритма и O-нотация
Оглавление:
Ты отправляешь решение олимпиадной задачи на проверку. Первые тесты проходят мгновенно, а на последнем система пишет: «Превышено ограничение времени». Программа не сломалась — просто на тесте с миллионом чисел ей нужна не секунда, а почти три часа.
Понять это заранее, не запуская программу, помогает сложность алгоритма — оценка того, как растет объем работы, когда данных становится больше.
Считаем операции, а не секунды
Время в секундах зависит от многого: от мощности компьютера, языка программирования, других запущенных программ. Поэтому скорость алгоритма меряют не секундомером, а числом элементарных операций: сравнений, присваиваний, сложений, обращений к элементу массива.
Число операций зависит от размера входных данных — его обозначают буквой $n$. Для массива $n$ — это количество элементов. Чтобы сложить все элементы, нужно $n$ сложений, а чтобы сравнить каждый элемент с каждым — около $n^2$ сравнений.
Обычно оценивают худший случай. Линейный поиск может найти число с первой попытки, но гарантировать можно одно: он сделает не больше $n$ сравнений.
Что значит $O(...)$
Допустим, алгоритм делает $3n^2 + 5n + 7$ операций. При $n = 1000$ первое слагаемое дает 3 000 000, а два остальных вместе — всего 5007. Главное слагаемое решает все, поэтому младшие отбрасывают, а заодно и множитель 3: он зависит от того, что считать одной операцией. Остается $n^2$, и пишут: сложность алгоритма $O(n^2)$, читается «о большое от эн квадрат».
Ключевая идея: $O(...)$ показывает не точное число операций, а скорость роста. Если сложность $O(n^2)$, то при росте $n$ в 10 раз работы станет примерно в 100 раз больше.
Главные классы сложности:
- $O(1)$ — время не зависит от $n$: взять элемент
a[i], узнать длину спискаlen(a); - $O(\log n)$ — задача на каждом шаге уменьшается вдвое, как в бинарном поиске;
- $O(n)$ — один проход по массиву: сумма, поиск максимума, линейный поиск;
- $O(n \log n)$ — быстрые сортировки, в том числе встроенные
sorted()в Python иsort()в C++; - $O(n^2)$ — два вложенных цикла: сравнить все пары, сортировка пузырьком или выбором.
Как растет число операций
Логарифм здесь по основанию 2, числа округлены:
| Сложность | $n = 10$ | $n = 1000$ | $n = 1\,000\,000$ |
|---|---|---|---|
| $O(1)$ | 1 | 1 | 1 |
| $O(\log n)$ | 3 | 10 | 20 |
| $O(n)$ | 10 | 1000 | 1 000 000 |
| $O(n \log n)$ | 33 | 10 000 | 20 000 000 |
| $O(n^2)$ | 100 | 1 000 000 | 1 000 000 000 000 |
Компьютер выполняет порядка $10^8$ простых операций в секунду (это для C++, Python в десятки раз медленнее). При миллионе элементов алгоритм за $O(n \log n)$ справится за доли секунды, а за $O(n^2)$ будет работать около $10^4$ секунд — почти три часа. Вот что случилось с решением из начала статьи.
Отсюда правило для олимпиад: при $n$ до нескольких тысяч пройдет и $O(n^2)$, а при $n$ около $10^6$ нужен $O(n)$ или $O(n \log n)$.
Как оценить сложность по коду
- Действия без циклов стоят $O(1)$.
- Цикл из $n$ шагов умножает стоимость тела на $n$. Вложенные циклы перемножаются: $n \cdot n = n^2$.
- Части, которые идут друг за другом, складываются, и остается самая тяжелая: $O(n) + O(n^2) = O(n^2)$.
- Если переменная цикла каждый раз делится пополам, шагов будет около $\log_2 n$.
Проверим правила: посчитаем шаги трех циклов при разных $n$.
def halving(n): # O(log n): делим n пополам
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
def linear(n): # O(n): один проход
steps = 0
for i in range(n):
steps += 1
return steps
def pairs(n): # O(n^2): все пары (i, j)
steps = 0
for i in range(n):
for j in range(n):
steps += 1
return steps
for n in [10, 1000]:
print(n, halving(n), linear(n), pairs(n))
# 10 3 10 100
# 1000 9 1000 1000000
То же на C++:
#include <iostream>
using namespace std;
long long halving(long long n) { // O(log n)
long long steps = 0;
while (n > 1) {
n /= 2;
steps++;
}
return steps;
}
long long linear(long long n) { // O(n)
long long steps = 0;
for (long long i = 0; i < n; i++) steps++;
return steps;
}
long long pairs(long long n) { // O(n^2)
long long steps = 0;
for (long long i = 0; i < n; i++)
for (long long j = 0; j < n; j++) steps++;
return steps;
}
int main() {
long long sizes[] = {10, 1000};
for (long long n : sizes)
cout << n << " " << halving(n) << " " << linear(n) << " " << pairs(n) << "\n";
// 10 3 10 100
// 1000 9 1000 1000000
}
Пример посложнее: есть ли в массиве одинаковые числа? Сравним a[i] с каждым элементом правее. Если повторов нет, сравнений будет $(n - 1) + (n - 2) + \ldots + 1 = \frac{n(n - 1)}{2} = \frac{n^2}{2} - \frac{n}{2}$. Отбрасываем множитель и младшее слагаемое: $O(n^2)$. Быстрее — сначала отсортировать массив за $O(n \log n)$: одинаковые числа окажутся рядом, и хватит одного прохода по соседям. Итого $O(n \log n) + O(n) = O(n \log n)$.
Частая ошибка: Пропустить скрытый цикл. Проверка
x in aдля списка,a.index(x),a.count(x), срезa[1:]сами проходят по списку и стоят $O(n)$. Внутри цикла по тому же списку они дают $O(n^2)$, хотя вложенного цикла в коде не видно. И наоборот: два цикла друг за другом — это $O(n) + O(n) = O(n)$, а не $O(n^2)$.
Проверь себя
В программе сначала идет цикл for i in range(n), а после него — еще один такой же цикл for j in range(n). В каждом цикле одна операция. Какая сложность у программы?
Алгоритм работает за $O(n^2)$. Во сколько раз примерно вырастет число операций, если $n$ увеличить в 10 раз?
Соедини сложность и пример алгоритма.
$O(1)$
Встроенная сортировка sorted()
$O(\log n)$
Найти максимум в массиве
$O(n)$
Сравнить каждый элемент с каждым
$O(n \log n)$
Взять элемент массива по индексу
$O(n^2)$
Бинарный поиск в отсортированном массиве