Основы временной сложности - Язык программирования C++ для спортивного программирования
Неделя 4Массивы и Векторы, Обход массива, Основы временной сложности
Основы временной сложности
Подсчёт шагов программы для самого большого ввода и сравнение с примерно 10⁸ в секунду: что говорят ограничения, почему проход по всему вектору для каждого элемента медленный, пометки в векторе вместо поиска, поддержание ответа в актуальном состоянии, O(1), O(n) и O(n²) и память.
Теория
Урок 6 из 8
12 мин чтения
Вопросов: 5
Две программы могут обе печатать правильный ответ, а проверяющая система всё
равно примет одну и отвергнет другую с вердиктом Time Limit Exceeded. Система
даёт каждому тесту около секунды, а некоторым правильным программам нужны часы.
Этот урок о том, как увидеть это до отправки: прикиньте, сколько шагов
сделает программа на самом большом вводе, который допускает условие, и сравните
с тем, что компьютер успевает за секунду.
Считаем шаги
Секунды мы не считаем — они зависят от компьютера. Мы считаем шаги: простые
действия вроде сложения, сравнения, чтения или изменения одной ячейки. Важно то,
как число шагов растёт с размером ввода n:
Код
Шагов для ввода размера n
a[i] = 7;, cout << a[p - 1];, x = x * 2 + 1;
несколько — одинаково при любом n
цикл по вектору: for (int i = 0; i < n; i++)
около n
два цикла один за другим
около 2n — всё равно «около n»
цикл, который на каждом проходе запускает ещё один цикл по вектору
около n · n = n²
Правило, которое делает всё это полезным:
Компьютер делает около 10⁸ простых шагов в секунду.
Это грубая оценка — быстрый компьютер на простых шагах успевает больше, — но
планировать по ней безопасно. Значит, при ограничении времени 1 секунда и n
до 10⁵:
дальше
Практика: Временная сложность
Три задачи, в которых очевидная программа верна, но слишком медленна.
около 100 секунд — далеко за пределами ограничения
Ограничения подсказывают, насколько быстрым надо быть
В каждом условии указан самый большой ввод, например 1 ≤ n ≤ 10⁵. Подставьте
его в число шагов до того, как писать программу:
Наибольшее n
n шагов
n² шагов
Что укладывается в секунду
100
100
10 000
всё разумное
5 000
5 000
2,5 · 10⁷
n² подходит
10⁵
10⁵
10¹⁰
только около n шагов (несколько проходов)
10⁶
10⁶
10¹²
только около n шагов, и с быстрым вводом
Ограничение 10⁵ — это условие, которое тихо говорит: «один или несколько
проходов по вводу, и никакого прохода по всему для каждого элемента». Ограничение
1000 или 5000 часто означает обратное: проход по всем элементам для каждого
элемента вполне ожидается.
Цикл, который каждый раз проходит целый цикл
У самой частой медленной программы одна и та же форма: для каждого элемента
она заново проходит по всем элементам. Циклы внутри циклов — тема недели 6;
здесь мы только считаем их шаги.
Кинотеатр продал билеты с номерами от 1 до n. После сеанса n - 1 из них
сдали обратно, в произвольном порядке. Билета с каким номером не хватает?
Первая идея: перебрать каждое число k от 1 до n и поискать его среди
билетов. Пройдите по шагам с тремя билетами — сюда добавлен счётчик сравнений:
Медленный способ: искать каждое число во всём векторе
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {3, 1};
9 int n = 3, checks = 0;
10 for (int k = 1; k <= n; k++) {
11 bool found = false;
12 for (int i = 0; i < n - 1; i++) {
13 checks++;
14 if (a[i] == k) {
15 found = true;
16 }
17 }
18 if (!found) {
19 cout << k << "\n";
20 }
21 }
22 cout << checks << " checks\n";
23 return 0;
24}
Билеты
строка 8
Проданы билеты с 1 по 3, а вернули два: 3 и 1. Какого не хватает?
a2 ячеек
3
1
0
1
n—checks—k—found—i—
нажми пуск
1 / 37
При n = 3 это 3 · 2 = 6 сравнений — пустяк. При n = 10⁵ это
10⁵ · (10⁵ − 1), около 10¹⁰ сравнений: примерно 100 секунд. Программа верна и
безнадёжна.
Исправление — перестать искать каждое число. Вместо этого пройдите по
билетам один раз и пометьте каждый номер как увиденный — в векторе, где
индексом служит сам номер билета:
Ввод
Вывод
seen[t] = true — это один шаг, и вопрос «был ли t?» — тоже один: никакого
поиска. Два цикла примерно по n шагов: 2 · 10⁵ шагов на самом большом вводе
вместо 10¹⁰. vector<bool> хранит в каждой ячейке true / false; это
работает, потому что значения — небольшие числа (не больше n), которые могут
служить индексами.
Есть и второй быстрый способ — арифметический: все числа от 1 до n в сумме дают
n · (n + 1) / 2 (формула Гаусса с недели 3), поэтому недостающий номер — это
эта сумма минус сумма сданных билетов. Не забудьте про long long: при
n = 10⁵ сумма около 5 · 10⁹ — а если n типа int, то n * (n + 1)
переполняется ещё до того, как результат сохранится, поэтому пишите
1LL * n * (n + 1) / 2 (неделя 1).
Та же гонка идёт в каждом классе. Предскажите, сколько шагов сделает каждая
учительница, посмотрите на них — и вынесите вердикт для 100 000 учеников.
Чьей тетради нет?попробуй!
Много раз повторяем маленький шаг
Та же ловушка прячется в «сделай это простое действие k раз». Циклический сдвиг
на одно место занимает около n шагов (прошлый урок). Сдвиг на k мест как
k сдвигов на одно занимает n · k шагов: при n и k до 10⁵ это снова 10¹⁰.
Если ставить каждый элемент сразу на его окончательное место,
b[(i + k) % n] = a[i], нужно n шагов при любом k.
Ещё хуже — моделировать процесс шаг за шагом, когда шагов огромное
количество. «Каждая операция увеличивает один элемент на 1; сколько операций
сделают все элементы равными?» Поднимать числа по единице может понадобиться до
10⁵ · 10⁹ операций. Но ответ — это сумма: каждый элемент должен дорасти до
максимума, для этого нужно mx - a[i] операций, а всего — сумма этих чисел: два
прохода, в long long.
Держим ответ в актуальном состоянии
Запросы, которые идут один за другим, — ещё одно место, где программа может
снова и снова переделывать одну и ту же работу:
Есть n банковских счетов с их остатками. Затем идут q операций p x:
остаток на счёте p становится равным x. После каждой операции выведите
сумму всех остатков.
Складывать все n остатков после каждой операции — это n · q шагов, 10¹⁰ при
n, q до 10⁵. Но одна операция меняет только один остаток, поэтому сумма
меняется ровно на разницу: старый остаток уходит из суммы, а новый приходит.
Ввод
Вывод
После первого цикла каждая операция стоит несколько шагов: всего n + q шагов.
На счёте 2 было 20, а стало 5, поэтому сумма 100 уменьшается на 15, до 85.
O(1), O(n), O(n²)
У этих оценок числа шагов есть названия. Мы оставляем только то, как быстро число
шагов растёт, и отбрасываем константу: и 3n шагов, и n + 5 шагов растут
как n. Это записывают как O(n) и читают «O от n».
Название
Как растёт
Пример из недель 3–4
O(1)
одинаково при любом n
a[p - 1], seen[t] = true, total += x - a[p - 1]
O(количества цифр)
почти не растёт: 19 шагов даже для 10¹⁸
цикл с % 10 / / 10
O(√n)
1000 шагов для 10⁶
проверка на простоту, которая останавливается на d * d <= n
O(n)
ввод вдвое больше — работы вдвое больше
проход по вектору или несколько проходов
O(n²)
ввод вдвое больше — работы вчетверо больше
для каждого элемента — проход по всем
Следить нужно именно за последней строкой. Если удвоить n, работа O(n)
удвоится, а работа O(n²) вырастет вчетверо — а если умножить n на 100, она
вырастет в 10 000 раз.
Теперь оцените несколько программ сами, раньше секундомера:
Вы — проверяющая системапопробуй!
У памяти тоже есть ограничение
В условиях указано и ограничение памяти, обычно 256 МБ. int занимает
4 байта, а long long — 8, поэтому вектор из 10⁵ или даже 10⁶ чисел совсем
маленький (4 МБ на миллион int). Проблемой это становится, только когда индексом
вектора служит огромное значение: чтобы помечать числа до 10⁹ в векторе
seen, понадобился бы миллиард ячеек — 4 ГБ, если это int. Пометки работают,
когда значения небольшие, до нескольких миллионов.
Проверьте себя
А вы знали?
Грейс Хоппер, одна из первых программисток, раздавала на своих выступлениях
кусочки провода длиной около 30 сантиметров. Каждый был наносекундой —
расстоянием, которое свет проходит за миллиардную долю секунды. Простейшие
операции процессора занимают примерно столько; один шаг настоящей программы со
всем, что вокруг него, — несколько таких, отсюда и правило примерно 10⁸ шагов в
секунду. Для сравнения она приносила моток длиной около 300 метров —
микросекунду, тысячу наносекунд.
проверь себя1 балл
n равно 10⁵. Для каждого из n элементов программа снова проходит по всем n элементам. Примерно сколько это шагов?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
При n ≤ 2000 и ограничении времени 1 секунда программа, которая сравнивает каждый элемент с каждым другим (около n² шагов), успевает.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Остатки на счетах — 10 20 30 40, total равно 100. Затем на счёте 3 становится 5, и программа делает total += 5 - a[2], прежде чем изменить a[2]. Чему теперь равно total?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Программа читает n чисел в вектор, одним циклом находит максимум, а вторым считает, сколько раз он встречается. Как растёт число её шагов?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В условии сказано 1 ≤ n ≤ 2 · 10⁵, ограничение времени — 1 секунда. Какой план подходит?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
6
4 1 6 2 3
5
4 3
10 20 30 40
2 5
4 0
1 100
85
45
135
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<bool> seen(n + 1, false); // seen[t]: нашёлся ли билет t? (seen[0] не используется) for(int i = 0; i < n - 1; i++){ int t; cin >> t; seen[t] = true; // один шаг, каким бы большим ни было n} for(int t = 1; t <= n; t++){ if(!seen[t]){ cout << t << "\n";}} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n, q; cin >> n >> q; vector<long long> a(n); long long total = 0; for(int i = 0; i < n; i++){ cin >> a[i]; total += a[i]; // складываем один раз, в начале} for(int k = 0; k < q; k++){ int p; long long x; cin >> p >> x; total += x - a[p - 1]; // старый остаток уходит, новый приходит a[p - 1] = x; cout << total << "\n";} return 0;}