Временная сложность на практике - Язык программирования C++ для спортивного программирования
ДополнительноОтладка и Стресс-тестирование
Временная сложность на практике
Продолжение недели 4: от ограничений к допустимой сложности (n!, 2ⁿ, n³, n², n log n, n, √n, log n), точный подсчёт вложенных циклов, гармонический цикл d, 2d, 3d…, циклы с делением пополам и log n, скрытые затраты одной строки, почему push_back в среднем быстрый, почему endl медленный и как засечь время на самом большом тесте.
Теория
Урок 2 из 3
13 мин чтения
Вопросов: 5
Неделя 4 научила считать шаги программы для самого большого ввода и сравнивать
их число примерно с 10⁸ простых шагов в секунду. Этот урок применяет то же
правило в обратную сторону: читает ограничения в условии и говорит, какие идеи
могут уложиться, ещё до того, как вы что-то придумали. Потом он считает циклы, о
которых неделя 4 не говорила, — циклы, которые делят пополам, циклы, у которых
внутренняя часть укорачивается, — и затраты, которые прячутся в одной строке
C++.
От ограничений к идее
Авторы выбирают ограничения так, чтобы задуманное решение укладывалось, а
очевидное более медленное — нет. При ограничении времени около секунды самое
большое n — сильная подсказка:
Самое большое n
Что укладывается в секунду
Шагов при этом n
Типичная идея
10
n! — все порядки
10! ≈ 3,6 · 10⁶
next_permutation по всем порядкам (неделя 8)
20
2ⁿ и даже 2ⁿ · n — все подмножества
2²⁰ ≈ 10⁶
построить все ответы рекурсией (неделя 9)
500
n³ — все тройки
500³ = 1,25 · 10⁸
три вложенных цикла
5 000
n² — все пары
2,5 · 10⁷
дальше
Стресс-тестирование
Продолжение недели 12: файл решения в том виде, в каком его отправляют, против файла с перебором на тестах генератора, запуск скриптом в Linux (bash) и Windows (.bat); номер теста как зерно, уменьшение теста с ошибкой, чекер, когда правильных ответов несколько, и самый большой тест — на переполнение и время.
сортировка, бинарный поиск для каждого элемента, set и map (недели 8, 11)
от 10⁷ до 10⁸
n, с простыми шагами
10⁸
один проход, быстрый ввод и вывод
10¹²
√n
10⁶
делители до √n (неделя 4)
10¹⁸
log n или формула
60
деление пополам, цифры, арифметика
Читайте таблицу в обе стороны. При n ≤ 5000 ожидается цикл по всем парам, и
искать что-то хитрее — значит терять время на контесте. При n ≤ 2 · 10⁵ цикл по
всем парам — это 2 · 10¹⁰ шагов, то есть автор говорит вам, что очевидная идея —
не ответ. Если во вводе два размера — n чисел и q вопросов, — перемножьте их:
n · q стоит идея «на каждый вопрос — проход по всем числам». А если тестов t,
проверьте, ограничивает ли условие сумму n по всем тестам; обычно да, и
тогда именно эта сумма — то n, которое надо подставлять.
Таблица — ориентир, а не закон. Совсем простых шагов в секунду выполняется больше 10⁸, а тяжёлых, например операций с map или %, — меньше.
Точный подсчёт вложенных циклов
Неделя 4 считала цикл внутри цикла как n · n. Часто внутренний цикл короче, и
полезно знать, насколько:
Циклы
Оборотов внутренней части
Для n из таблицы
i от 0 до n − 1, j от i + 1 до n − 1
n(n − 1) / 2 — каждая пара один раз
n = 5000: 12 497 500
i<j<k, три цикла
n(n − 1)(n − 2) / 6 — каждая тройка один раз
n = 500: 20 708 500
i по n элементам, c по 26 буквам
26 · n
n = 10⁶: 2,6 · 10⁷
d от 1 до n, m = d, 2d, 3d, … до n
n/1 + n/2 + n/3 + … ≈ n · ln n
n = 10⁶: 13 970 034
Последняя строка — сюрприз: выглядит как n², но внутренний цикл шагает всё
шире. Вот где это окупается:
Для каждого числа от 1 до n напечатайте, сколько у него делителей.
1 ≤ n ≤ 10⁶.
Ввод
Вывод
Если искать делители каждого числа до его квадратного корня, как в неделе 4, на
каждое x уйдёт около √x шагов — примерно 6,7 · 10⁸ шагов при n = 10⁶.
Переверните вопрос: вместо того чтобы спрашивать, какие числа делят x, пусть
каждое d пройдёт по числам, которые оно делит, — d, 2d, 3d и так далее:
Два цикла вместе делают n/1 + n/2 + … + n/n оборотов. Эта сумма примерно равна
n · ln n — при n = 10⁶ ровно 13 970 034 оборота, почти в пятьдесят раз меньше,
чем способом с корнем.
Циклы, которые делят пополам
Цикл, который каждый раз делит что-то пополам, заканчивается очень быстро.
Сколько раз можно разделить 100 пополам нацело, пока ничего не останется?
Сколько раз можно разделить 100 пополам?
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 int n;
6 cin >> n;
7 int steps = 0;
8 while (n > 0) {
9 n /= 2;
10 steps++;
11 }
12 cout << steps << "\n";
13 return 0;
14}
Читаем n
строка 6
n = 100. Сколько раз его можно делить пополам, пока ничего не останется?
ввод
100
n100steps—
нажми пуск
1 / 25
Семь оборотов. Каждый оборот делит n пополам, поэтому число оборотов — это
сколько раз можно разделить n пополам, примерно log₂ n, логарифм. Чтобы
почувствовать, как он мал, запомните один факт: 2¹⁰ = 1024, примерно тысяча.
Поэтому:
n
примерно
Делений пополам
10³
2¹⁰
10
10⁶
2²⁰
20
10⁹
2³⁰
30
10¹⁸
2⁶⁰
60
Вот почему бинарному поиску (неделя 8), который делит пополам отрезок поиска,
хватает 20 шагов среди миллиона отсортированных чисел, и почему цикл, который
удваивает, for (long long p = 1; p <= n; p *= 2), делает не больше 60 оборотов
даже для 10¹⁸. Отсюда же берётся «log n» в n log n: сортировка n чисел стоит
около n · log₂ n сравнений, а каждая операция с set или map из n элементов —
около log₂ n шагов, так что n таких операций стоят n log n —
2 · 10⁵ · 18 ≈ 3,6 · 10⁶.
Скрытые затраты в одной строке
Строка, которая выглядит как один шаг, может оказаться целым циклом. Вот самые
частые:
Строка
Сколько она стоит на самом деле
Вместо этого
s = s + c;
копирует всю s в новую строку: столько шагов, сколько в s символов
s += c; — добавляет один символ на месте
a.insert(a.begin(), x);, a.erase(a.begin());
сдвигает каждый элемент на одно место: n шагов
deque с push_front / pop_front (неделя 10) или работа с конца
count(a.begin(), a.end(), x) или find(…) внутри цикла
каждый раз проход по всему вектору
посчитать один раз, в векторе количеств или в map (неделя 11)
вызов f(vector<int> a) для каждого из n элементов
копирует вектор при каждом вызове
const vector<int> &a (неделя 7)
vector<int> cnt(1000001); внутри цикла по тестам
10⁶ шагов на каждый тест, даже крошечный
брать размер по значениям этого теста или очищать только то, что использовали
cout << x << endl;
заканчивает строку и сбрасывает вывод
cout << x << "\n";
a.size(), a[i], a.push_back(x), s += c
несколько шагов
—
Насколько велика разница? Мы собрали строку из 2 · 10⁵ символов обоими
способами и засекли время: s = s + c заняло около 1,2 секунды, s += c —
около 0,05, и большая часть этих 0,05 — просто запуск программы.
Почему push_back всё равно быстрый
Вектор хранит элементы рядом, в одном блоке памяти. Когда блок заполнен, а вы
делаете ещё один push_back, вектор получает новый, больший блок, копирует в
него всё и освобождает старый. Похоже на n шагов на один push_back. Посмотрите,
как часто это происходит на самом деле:
capacity() — это размер блока. Каждый раз, когда он заполняется, новый блок
получается вдвое больше (в g++; другие компиляторы увеличивают его примерно
так же). Поэтому за 100 вызовов push_back вектор получал новый блок всего 8
раз, а копирований набралось 1 + 2 + 4 + … + 64 = 127 — меньше двух на элемент.
Как бы ни рос вектор, push_back стоит несколько шагов в среднем: дорогое
копирование случается так редко, что, если разделить его на все дешёвые вызовы,
на каждый придётся меньше двух шагов. Это называется амортизированным O(1).
Если вы знаете итоговый размер, a.reserve(n); сразу получает блок нужного
размера и обходится без копирований.
Почему endl медленный
endl делает две вещи: заканчивает строку и сбрасывает вывод — отправляет
всё, что ждёт в буфере cout, на экран или в файл прямо сейчас. Запись наружу —
медленная операция, и буфер существует, чтобы она происходила большими
порциями. endl ломает это на каждой строке. Мы напечатали числа от 1 до 10⁶ по
одному в строке в файл: с endl это заняло около 2,6 секунды, с "\n" — около
0,4.
Строки быстрого ввода делают нечто похожее. cin.tie(NULL) отменяет сброс
cout перед каждым чтением из cin, а ios_base::sync_with_stdio(false)
позволяет cin и cout держать свои буферы, а не работать в согласии с scanf
и printf из C. Для этого и нужны две строки из шаблона — и поэтому после них
не стоит смешивать в одной программе cin со scanf или cout с printf.
Измеряйте, а не гадайте
Подсчёт шагов говорит, может ли идея уложиться. Замер времени на самом
большом тесте говорит, укладывается ли ваш код. Сделайте тест маленькой
программой, которая его печатает (или одним числом, как 10⁶ в задаче про
делители), сохраните в файл и запустите на нём решение:
Задача про делители при n = 10⁶ заняла на нашем компьютере около 1,2 секунды
способом с корнем и 0,35 секунды способом с кратными — и большая часть этих 0,35
секунды ушла на печать миллиона чисел. Компьютер проверяющей системы может
оказаться быстрее или медленнее вашего, поэтому дома ориентируйтесь не больше
чем на половину ограничения времени.
Проверьте себя
А вы знали?
Буква O в O(n) старше компьютеров. Немецкий математик Пауль Бахман использовал
её в 1894 году в книге по теории чисел, а Эдмунд Ландау сделал её популярной в
1909 году. Дональд Кнут сделал её стандартом в информатике: в 1976 году он
опубликовал короткую статью, в которой заодно закрепил смысл двух её спутников —
Ω для «не меньше» и Θ для «ровно так», — поэтому программисты до сих пор говорят
«O большое».
проверь себя1 балл
В условии n ≤ 20, ограничение времени — 1 секунда. На какую идею намекают такие ограничения?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Сколько оборотов сделает этот цикл при n = 1000?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Примерно сколько оборотов сделает внутренний цикл в сумме при n = 10⁶?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Строка из 2 · 10⁵ символов, которую собирают по одному символу, строится с s = s + c; примерно так же быстро, как с s += c;.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Вы начинаете с пустого вектора и вызываете push_back n раз. Примерно сколько шагов займут все вызовы вместе?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
В Linux или macOS:
time ./sol < big.txt > out.txt
В Windows, в PowerShell:
Measure-Command { cmd /c ".\sol.exe < big.txt > out.txt" }
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> cnt(n + 1, 0); for(int d = 1; d <= n; d++){ for(int m = d; m <= n; m += d){ cnt[m]++; // d делит m}} for(int x = 1; x <= n; x++){ cout << cnt[x]<< " ";} cout << "\n"; return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ vector<int> a; int cap = a.capacity(); for(int x = 1; x <= 100; x++){ a.push_back(x); if((int)a.capacity() != cap){ // вектор переехал в блок побольше cap = a.capacity(); cout << "size "<< a.size()<< ": capacity "<< cap << "\n";}} return 0;}
int steps = 0;while(n > 0){ n /= 2; steps++;}
for(int d = 1; d <= n; d++){ for(int m = d; m <= n; m += d){ cnt[m]++;}}