Проектирование алгоритмов. По сути своей, олимпиадное программирование — это придумывание эффективных алгоритмов решения корректно поставленных вычислительных задач. Для проектирования алгоритмов необходимы навыки в решении задач и знание математики. Зачастую решение появляется в результате сочетания хорошо известных методов и новых идей. Важную роль в олимпиадном программировании играет математика. На самом деле четких границ между проектированием алгоритмов и математикой не существует.

Реализация алгоритмов. В олимпиадном программировании решение задачи оценивается путем проверки реализованного алгоритма на ряде тестов. Поэтому придумать алгоритм недостаточно, его еще нужно корректно реализовать, для чего требуется умение программировать. Олимпиадное программирование сильно отличается от традиционной программной инженерии: программы короткие (несколько сотен строк – уже редкость), писать их нужно быстро, а сопровождение после соревнования не требуется. В настоящее время на соревнованиях по программированию популярнее всего языки C++, Python и Java.

Чтобы научиться олимпиадному программированию, нужно напряженно работать. Но способов приобрести практический опыт много, одни лучше, другие хуже. Решая задачи, нужно иметь в виду, что не так важно количество решенных задач, как их качество. Возникает соблазн выбирать красивые и легкие задачи, пропуская те, что кажутся трудными и требующими кропотливого труда. Но чтобы отточить свои навыки, нужно отдавать предпочтение именно задачам второго типа. Важно и то, что большинство олимпиадных задач решается с помощью простого и короткого алгоритма, самое трудное – придумать этот алгоритм. Смысл олимпиадного программирования – не в заучивании сложных и малопонятных алгоритмов, а в том, чтобы научиться решать трудные задачи, обходясь простыми средствами. Наконец, есть люди, презирающие реализацию алгоритмов, им доставляет удовольствие проектировать алгоритмы, а реализовывать их скучно. Однако умение быстро и правильно реализовать алгоритм – важное преимущество, и этот навык поддается тренировке. Будет очень плохо, если вы потратите большую часть отведенного времени на написание кода и поиск ошибок, а не на обдумывание того, как решить задачу.

Соревнования по программированию

Международная олимпиада по информатике (IOI) – ежегодное соревнование для старшеклассников. От каждой страны допускается команда из четырех человек. Обычно набирается около 300 участников из 80 стран. IOI проводится в течение двух дней. В каждый день участникам предлагается решить три трудные задачи, на решение отводится пять часов. Задачи разбиты на подзадачи, за каждую из которых начисляются баллы. Хотя участники являются членами команды, соревнуются они самостоятельно. Участники IOI отбираются на национальных олимпиадах. IOI предшествует множество региональных соревнований, например: Балтийская олимпиада по информатике (BOI), Центрально-Европейская олимпиада по информатике (CEOI) и Азиатско-Тихоокеанская олимпиада по информатике (APIO).

ICPC (Международная студенческая олимпиада по программированию) проводится ежегодно для студентов университетов. В каждой команде три участника; в отличие от IOI, студенты работают вместе, и каждой команде выделяется только один компьютер. ICPC включает несколько этапов, лучшие команды приглашаются на финальный этап мирового первенства. Хотя в соревновании принимают участие тысячи студентов, количество участников финала ограничено, поэтому даже сам выход в финал считается большим достижением. На соревновании ICPC у команды есть пять часов на решение примерно десяти алгоритмических задач. Решение засчитывается, только если программа прошла все тесты и показала свою эффективность. В ходе соревнования участники могут видеть результаты соперников, но в начале пятого часа табло замораживается, и результаты последних прогонов не видны.

Онлайновые соревнования. Существует также много онлайновых соревнований, куда допускаются все желающие. В настоящий момент наиболее активен сайт Codeforces, который организует конкурсы почти каждую неделю. Отметим также сайты AtCoder, CodeChef, CS Academy, HackerRank и Topcoder. Некоторые компании организуют онлайновые соревнования с очными финалами, например: Facebook Hacker Cup, Google Code Jam и Yandex.Algorithm. Разумеется, компании используют такие соревнования для подбора кадров: достойно выступить в соревновании – хороший способ доказать свои таланты в программировании.

Языковые средства (С++)

Ввод-вывод

В большинстве олимпиадных задач для ввода и вывода используются стандартные потоки. В C++ стандартный поток ввода называется cin, а стандартный поток вывода – cout. Входными данными для программы обычно являются числа и строки, разделенные пробелами и знаками новой строки. Из потока cin они читаются следующим образом:

  int a, b;
  string x;
  cin >> a >> b >> x;

Такой код работает в предположении, что элементы потока разделены хотя бы одним пробелом или знаком новой строки.

Поток cout используется для вывода:

 int a = 123, b = 456;
 string x = "monkey";
 cout << a << " " << b << " " << x << "\n";

Ввод и вывод часто оказываются узкими местами программы. Чтобы повысить эффективность ввода-вывода, можно поместить в начало программы такие строки:

 ios_base::sync_with_stdio(false);
 cin.tie(0);

Отметим, что знак новой строки “\n” работает быстрее, чем endl, потому что endl всегда сопровождается сбросом буфера.

Иногда программа должна прочитать целую входную строку, быть может, содержащую пробелы. Это можно сделать с помощью функции getline:

 string s;
 getline(cin, s);

Если объем данных заранее неизвестен, то полезен такой цикл:

while (cin >> x) {
	// код
}

Этот цикл читает из стандартного ввода элементы один за другим, пока входные данные не закончатся.

В некоторых олимпиадных системах для ввода и вывода используются файлы. В таком случае есть простое решение: писать код так, будто работаешь со стандартными потоками, но в начало программы добавить такие строки:

 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);

После этого программа будет читать данные из файла "input.txt", а записывать в файл "output.txt".

Работа с числами

Представление целых чисел в компьютере

Целые числа могут представляться в компьютере со знаком или без знака.

Рассмотрим особенности записи целых чисел со знаком на примере однобайтового формата, при котором для знака отводится один разряд, а для цифр абсолютной величины — семь разрядов.

В компьютерной технике применяются три формы записи (кодирования) целых чисел со знаком:

прямой код
обратный код
дополнительный код

Последние две формы применяются особенно широко, так как позволяют упростить конструкцию арифметико-логического устройства компьютера путем замены разнообразных арифметических операций операцией сложения.

Положительные числа в прямом, обратном и дополнительном кодах изображаются одинаково - двоичными кодами с цифрой 0 в знаковом разряде.

Например:

$1_{10} = 0\space0000001_2$

$127_{10} = 0\space1111111_2$

Отрицательные числа в прямом, обратном и дополнительном кодах имеют разное изображение.

Прямой код

В знаковый разряд помещается цифра 1, а в разряды цифровой части числа — двоичный код его абсолютной величины.

Например:

$1_{10} = 1\space0000001_2$

$-127_{10} = 1\space1111111_2$

Обратный код

Получается инвертированием всех цифр двоичного кода абсолютной величины числа, включая разряд знака: нули заменяются единицами, а единицы — нулями.

Например:

$1_{10} = 1\space1111110_2$

$-127_{10} = 1\space0000000_2$

Дополнительный код

Получается образованием обратного кода с последующим прибавлением единицы к его младшему разряду.

Например:

$1_{10} = 1\space1111111_2$

$-127_{10} = 1\space0000001_2$

Обычно отрицательные десятичные числа при вводе в машину автоматически преобразуются в обратный или дополнительный двоичный код и в таком виде хранятся, перемещаются и участвуют в операциях. При выводе таких чисел из машины происходит обратное преобразование в отрицательные десятичные числа.

Выполнение арифметических действий над целыми числами в компьютере

Сложение и вычитание

В большинстве компьютеров операция вычитания не используется. Вместо нее производится сложение обратных или дополнительных кодов уменьшаемого и вычитаемого. Это позволяет существенно упростить конструкцию АЛУ.

Сложение обратных кодов. Здесь при сложении чисел А и В имеют место четыре основных и два особых случая:

А и В положительные. При суммировании складываются все разряды, включая разряд знака. Так как знаковые разряды положительных слагаемых равны нулю, разряд знака суммы тоже равен нулю.

Получен правильный результат.

А положительное, B отрицательное и по абсолютной величине больше, чем А.

Получен правильный результат в обратном коде. При переводе в прямой код биты цифровой части результата инвертируются: $1\space0000111_2 = -7_{10}$ .

А положительное, B отрицательное и по абсолютной величине меньше, чем А.

Компьютер исправляет полученный первоначально неправильный результат (6 вместо 7) переносом единицы из знакового разряда в младший разряд суммы.

А и В отрицательные.

Полученный первоначально неправильный результат (обратный код числа $-1110_2$ вместо обратного кода числа $-1010_2$ ) компьютер исправляет переносом единицы из знакового разряда в младший разряд суммы. При переводе результата в прямой код биты цифровой части числа инвертируются: $1\space0001010_2 = -10_{10}$ .

При сложении может возникнуть ситуация, когда старшие разряды результата операции не помещаются в отведенной для него области памяти. Такая ситуация называется переполнением разрядной сетки формата числа. Для обнаружения переполнения и оповещения о возникшей ошибке в компьютере используются специальные средства.

Ниже приведены два возможных случая переполнения.

А и В положительные, сумма А + В больше, либо равна $2^{n - 1}$ , где n — количество разрядов формата чисел (для однобайтового формата $n = 8, 2^{n - 1} = 2^7 = 128$ ).

Семи разрядов цифровой части числового формата недостаточно для размещения восьмиразрядной суммы ( $162_{10} = 1\space0100010_2$ ), поэтому старший разряд суммы оказывается в знаковом разряде. Это вызывает несовпадение знака суммы и знаков слагаемых, что является свидетельством переполнения разрядной сетки.

А и В отрицательные, сумма абсолютных величин А и В больше, либо равна $2^{n-1}$ .

Здесь знак суммы тоже не совпадает со знаками слагаемых, что свидетельствует о переполнении разрядной сетки.

Сложение дополнительных кодов. Здесь также имеют место рассмотренные выше шесть случаев:

А и В положительные. Здесь нет отличий от случая 1, рассмотренного для обратного кода.
2) А положительное, B отрицательное и по абсолютной величине больше, чем А.

Получен правильный результат в дополнительном коде. При переводе в прямой код биты цифровой части результата инвертируются и к младшему разряду прибавляется единица: $1\space0000110_2 + 1_2 = 1\space0000111_2 = -7_{10}$ .

А положительное, B отрицательное и по абсолютной величине меньше, чем А.

Получен правильный результат. Единицу переноса из знакового разряда компьютер отбрасывает.

А и В отрицательные.

Получен правильный результат в дополнительном коде. Единицу переноса из знакового разряда компьютер отбрасывает.

Случаи переполнения для дополнительных кодов рассматриваются по аналогии со случаями 5 и 6 для обратных кодов.

Сравнение рассмотренных форм кодирования целых чисел со знаком показывает:

на преобразование отрицательного числа в обратный код компьютер затрачивает меньше времени, чем на преобразование в дополнительный код, так как последнее состоит из двух шагов — образования обратного кода и прибавления единицы к его младшему разряду;
время выполнения сложения для дополнительных кодов чисел меньше, чем для их обратных кодов, потому что в таком сложении нет переноса единицы из знакового разряда в младший разряд результата.

Умножение и деление

Во многих компьютерах умножение производится как последовательность сложений и сдвигов. Для этого в АЛУ имеется регистр, называемый накапливающим сумматором, который до начала выполнения операции содержит число ноль. В процессе выполнения операции в нем поочередно размещаются множимое и результаты промежуточных сложений, а по завершении операции — окончательный результат.

Другой регистр АЛУ, участвующий в выполнении этой операции, вначале содержит множитель. Затем по мере выполнения сложений содержащееся в нем число уменьшается, пока не достигнет нулевого значения.

Для иллюстрации умножим $110011_2$ на $101101_2$ .

Деление для компьютера является трудной операцией. Обычно оно реализуется путем многократного прибавления к делимому дополнительного кода делителя.

Представление вещественных чисел в компьютере

Система вещественных чисел в математических вычислениях предполагается непрерывной и бесконечной, т.е. не имеющей ограничений на диапазон и точность представления чисел. Однако в компьютерах числа хранятся в регистрах и ячейках памяти с ограниченным количеством разрядов. Вследствие этого система вещественных чисел, представимых в машине, является дискретной (прерывной) и конечной.

При написании вещественных чисел в программах вместо привычной запятой принято ставить точку. Для отображения вещественных чисел, которые могут быть как очень маленькими, так и очень большими, используется форма записи чисел с порядком основания системы счисления. Например, десятичное число 1.25 в этой форме можно представить так:

$1.25・10^0 = 0.125・10^1 = 0.0125・10^2 = ...$ или так:

$12.5・10^{-1} = 125.0・10^{-2} = 1250.0・10^{-3} = ...$

Любое число N в системе счисления с основанием q можно записать в виде $N = M・ q^p$ , где M — множитель, содержащий все цифры числа (мантисса), а p — целое число, называемое порядком. Такой способ записи чисел называется представлением числа с плавающей точкой.

Если "плавающая" точка расположена в мантиссе перед первой значащей цифрой, то при фиксированном количестве разрядов, отведенных под мантиссу, обеспечивается запись максимального количества значащих цифр числа, то есть максимальная точность представления числа в машине. Из этого следует: Мантисса должна быть правильной дробью, у которой первая цифра после точки (запятой в обычной записи) отлична от нуля: $0.12 ≤ |M| < 1$ . Если это требование выполнено, то число называется нормализованным.

Мантиссу и порядок $q$ -ичного числа принято записывать в системе с основанием q, а само основание — в десятичной системе.

Вещественные числа в компьютерах различных типов записываются по-разному, тем не менее, все компьютеры поддерживают несколько международных стандартных форматов, различающихся по точности, но имеющих одинаковую структуру следующего вида:

Здесь порядок $n$ -разрядного нормализованного числа задается в так называемой смещенной форме: если для задания порядка выделено k разрядов, то к истинному значению порядка, представленного в дополнительном коде, прибавляют смещение, равное $(2^{k - 1} - 1)$ .

Например, порядок, принимающий значения в диапазоне от $-128$ до $+127$ , представляется смещенным порядком, значения которого меняются от 0 до 255. Использование смещенной формы позволяет производить операции над порядками, как над беззнаковыми числами, что упрощает операции сравнения, сложения и вычитания порядков, а также упрощает операцию сравнения самих нормализованных чисел.

Чем больше разрядов отводится под запись мантиссы, тем выше точность представления числа. Чем больше разрядов занимает порядок, тем шире диапазон от наименьшего отличного от нуля числа до наибольшего числа, представимого в машине при заданном формате.

Следует отметить, что вещественный формат с $m$ -разрядной мантиссой позволяет абсолютно точно представлять $m$ -разрядные целые числа, т. е. любое двоичное целое число, содержащее не более m разрядов, может быть без искажений преобразовано в вещественный формат.

Целые числа в С++

Из целых типов в олимпиадном программировании чаще всего используется int – $32$ -разрядный тип, принимающий значения из диапазона − $2^{31} ... 2^{31} − 1$ (приблизительно $−2 · 10^9 ... 2 · 10^9$ ). Если типа int недостаточно, то можно взять $64$ -разрядный тип long long. Диапазон его значений − $2^{63} ... 2^{63} − 1$ (приблизительно $−9 · 10^{18} ... 9 · 10^{18}$ ). Ниже определена переменная типа long long:

 long long x = 123456789123456789LL;

Суффикс LL означает, что число имеет тип long long. Типичная ошибка при использовании типа long long возникает, когда где-то в программе встречается еще и тип int. Например, в следующем коде есть тонкая ошибка:

 int a = 123456789;
 long long b = a*a;
 cout << b << "\n"; // -1757895751

Хотя переменная b имеет тип long long, оба сомножителя в выражении $a · a$ имеют тип int, поэтому тип результата тоже int. Из-за этого значение b оказывается неверным. Проблему можно решить, изменив тип a на long long или изменив само выражение на (long long)a · a.

Обычно олимпиадные задачи формулируются так, что типа long long достаточно. Но все же полезно знать, что компилятор g++ поддерживает также 128-разрядный тип __int128_t с диапазоном значений $−2^{127} ... 2^{127} − 1$ (приблизительно $−10^{38} ... 10^{38}$ ). Однако этот тип доступен не во всех олимпиадных системах.

Арифметика по модулю

Иногда ответом является очень большое число, но достаточно вывести результат «по модулю $m$ », т. е. остаток от деления на $m$ (например, « $7$ по модулю $109$ »). Идея в том, что даже когда истинный ответ очень велик, типов int и long long все равно достаточно. Остаток $x$ от деления на $m$ обозначается $x\space mod\space m$ . Например, $17\space mod\space 5 = 2$ , поскольку $17 = 3 · 5 + 2$ . Важные свойства остатков выражаются следующими формулами:

$(a + b)\space mod\space m = (a\space mod\space m + b\space mod\space m)\space mod\space m;$

$(a − b)\space mod\space m = (a\space mod\space m − b\space mod\space m)\space mod\space m;$

$(a · b)\space mod\space m = (a\space mod\space m · b\space mod\space m)\space mod\space m.$

Это значит, что можно брать остаток после каждой операции, поэтому числа никогда не станут слишком большими.

Числа с плавающей точкой в C++

В большинстве олимпиадных задач целых чисел достаточно, но иногда возникает потребность в числах с плавающей точкой. В C++ наиболее полезен $64$ -разрядный тип double, а в компиляторе g++ имеется расширение – $80$ -разрядный тип long double. Чаще всего типа double достаточно, но long double дает более высокую точность. Требуемая точность ответа обычно указывается в формулировке задачи. Для вывода ответа можно использовать:

#include <iomanip>
cout << setprecision(5); // Вывод до 5 символа
cout << fixed; // Вывод в фиксированной форме(без экспоненты)

Числа с плавающей точкой рискованно сравнивать с помощью оператора $==$ , потому что иногда равные значения оказываются различны из-за ошибок округления. Более правильно считать, что два числа равны, если разность между ними меньше $\epsilon$ , где $\epsilon$ мало. Например, в следующем коде $\epsilon = 10−9$ :

const double eps = 1e-9;
if (abs(a-b) < eps) {
	// a и b равны
}

Отметим, что хотя числа с плавающей точкой, вообще говоря, не точны, не слишком большие целые числа представляются точно. Так, тип double позволяет точно представить все целые числа, по абсолютной величине не большие $2^{53}$ .

Сокращение кода

Имена типов. Ключевое слово typedef позволяет сопоставить типу данных короткое имя. Например, имя long long слишком длинное, поэтому можно определить для него короткий псевдоним ll.

После этого код

long long a = 123456789;
long long b = 987654321;
cout << a*b << "\n";

можно немного сократить:

typedef long long ll;
ll a = 123456789;
ll b = 987654321;
cout << a * b << "\n";

Ключевое слово typedef применимо и к более сложным типам. Например, ниже мы сопоставляем вектору целых чисел имя vi, а паре двух целых чисел – тип pii.

typedef vector<int> vi;
typedef pair<int,int> pii;

Макросы. Еще один способ сократить код – макросы. Макрос говорит, что определенные строки кода следует подменить до компиляции. В C++ макросы определяются с помощью ключевого слова #define. Например, мы можем определить следующие макросы:

#define F first
#define S second
#define PB push_back
#define MP make_pair

После чего код

v.push_back({y1,x1});
v.push_back({y2,x2});
int d = v[i].first+v[i].second;

можно сократить до:

v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F+v[i].S;

У макроса могут быть параметры, что позволяет сокращать циклы и другие структуры. Например, можно определить такой макрос:

#define REP(i,a,b) for (int i = a; i <= b; i++)

После этого код

for (int i = 1; i <= n; i++) {
    search(i);
}

можно сократить следующим образом:

REP(i,1,n) {
    search(i);
}

Стоит отметить, что использование #define имеет множество минусов, например:

Неудобство в отладке
Засорение глобального пространства имён
Возможность возникновения всяких неприятных непредвиденных эффектов.

и его стоит избегать.

Побитовые операции

Сдвиг влево: “<<”: (x << y), все биты в $x$ сдвигаются влево на количество бит, представленное значением $y$ ;
Сдвиг вправо: “>>”: (x >> y), все биты в $x$ сдвигаются вправо на количество бит, представленное значением $y$ ;
Побитовое NOT: (~x), все биты в $x$ инвертируются;
Побитовое AND: (x & y), выполняется операция AND каждого бита в $x$ с каждым соответствующим битом в $y$ ;
Побитовое OR: (x | y), выполняется операция OR каждого бита в $x$ с каждым соответствующим битом в $y$ ;
Побитовое исключающее XOR: (x ^ y), выполняется операция XOR каждого бита в $x$ с каждым соответствующим битом в $y$ .

Дополнительные функции. Компилятор g++ предлагает также следующие функции для подсчета битов:

__builtin_clz(x); // количество нулей в начале двоичного представления
__builtin_ctz(x); // количество нулей в конце двоичного представления
__builtin_popcount(x); // количество единиц в двоичном представлении
__builtin_parity(x); // четность количества единиц в двоичном
представлении

Эти функции работают для int, для long long:

__builtin_clzll(x); // количество нулей в начале двоичного представления 
__builtin_ctzll(x); // количество нулей в конце двоичного представления 
__builtin_popcountll(x); // количество единиц в двоичном представлении 
__builtin_parityll(x); // четность количества единиц в двоичном представлении

Вычислительная сложность

В этой главе мы поговорим о том, как оценивать вычислительные ресурсы — такие как время и память — которые требуются для завершения алгоритмов.

Часто бывает полезно оценить, сколько времени работает алгоритм. Конечно, можно его просто реализовать и запустить, но тут возникают проблемы:

На разных компьютерах время работы всегда будет отличаться.
Не всегда заранее доступны именно те данные, на которых он в реальности будет запускаться.
Иногда приходится оценивать алгоритмы, требующие часы или даже дни работы.
Жизнь коротка, и если есть несколько вариантов алгоритмов, то хочется заранее предсказать, какой из них будет оптимально решать задачу, чтобы реализовывать только его.

Для этого, в качестве первого приближения, попробуем оценить число операций в алгоритме. Возникает вопрос: какие именно операции считать. Как один из вариантов — учитывать любые элементарные операции:

арифметические операции с числами: +, -, *, /
сравнение чисел: <, >, <=, >=, ==, !=
присваивание: a = 3

При этом важно не просто считать строчки, а ещё учитывать, как реализованы некоторые отдельные вещи в самом языке.

int a = 5, b = 10;
cout << a + b; // 1 операция

string a = "qwerty", b = "asdfgh";
cout << a + b; // 12 операций (пропорционально длине строк)

Подобный подсчет элементарных операций связан с очевидными трудности, а полученный результат не всегда годится для сравнения работы разных программ.

Хочется придумать способ упростить эти формулы так, чтобы:

Не нужно было учитывать информацию, не очень сильно влияющую на итоговое время;
Легко было оценивать время работы разных алгоритмов для больших чисел;
Легко было сравнивать алгоритмы на предмет того, какой из них лучше подходит для тех или иных входных данных.

Для этого используют следующий подход.

Временная сложность алгоритма – это оценка того, сколько времени будет работать алгоритм при заданных входных данных. Зная временную сложность, мы зачастую можем сказать, достаточно ли алгоритм быстрый для решения задачи, даже не реализуя его. Для описания временной сложности применяется нотация $O(...)$ , где многоточием представлена некоторая функция. Обычно буквой $n$ обозначается размер входных данных. Например, если на вход подается массив чисел, то $n$ – это размер массива, а если строка, то $n$ – длина строки.

Если код включает только линейную последовательность команд, как, например, показанный ниже, то его временная сложность равна $O(1)$ .

a++;
b++;
c = a+b;

Временная сложность цикла оценивает число выполненных итераций. Например, временная сложность следующего кода равна $O(n)$ , поскольку код внутри цикла выполняется $n$ раз. При этом предполагается, что многоточием «...» обозначен код с временной сложностью $O(1)$ .

for (int i = 1; i <= n; i++) {
    ...
}

Временная сложность следующего кода равна $O(n^2)$ :

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
		...
	}
}

Вообще, если имеется $k$ вложенных циклов и в каждом цикле перебирается n значений, то временная сложность равна $O(n^k)$ .

Временная сложность не сообщает, сколько точно раз выполняется код внутри цикла, она показывает лишь порядок величины, игнорируя постоянные множители.

В примерах ниже код внутри цикла выполняется $3n$ , $n + 5$ и $n/2$ раз, но временная сложность в каждом случае равна $O(n)$ .

for (int i = 1; i <= 3*n; i++) {
    ...
}
for (int i = 1; i <= n+5; i++) {
    ...
}
for (int i = 1; i <= n; i += 2) {
    ...
}

С другой стороны, временная сложность следующего кода равна $O(n^2)$ , поскольку код внутри цикла выполняется $1 + 2 + ... + n = (n2 + n)/2$ раз.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
		...
	}
}

Если алгоритм состоит из нескольких последовательных частей, то общая временная сложность равна максимуму из временных сложностей отдельных частей, т. е. самая медленная часть является узким местом. Так, следующий код состоит из трех частей с временной сложностью $O(n)$ , $O(n^2)$ и $O(n)$ . Поэтому общая временная сложность равна $O(n^2)$ .

for (int i = 1; i <= n; i++) {
	...
}
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		...
	}
}
for (int i = 1; i <= n; i++) {
	...
}

Иногда временная сложность зависит от нескольких факторов, поэтому формула включает несколько переменных. Например, временная сложность следующего кода равна $O(n · m)$

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= m; j++) {
		...
	}
}

Часто встречающиеся оценки временной сложности

$O(1)$ Время работы алгоритма с постоянным временем не зависит от размера входных данных. Типичным примером может служить явная формула, по которой вычисляется ответ.
$O(log\space n)$ В логарифмическом алгоритме размер входных данных на каждом шаге обычно уменьшается вдвое. Время работы зависит от размера входных данных логарифмически, поскольку $log_2\space n$ – это сколько раз нужно разделить $n$ на $2$ , чтобы получить $1$ . Отметим, что основание логарифма во временной сложности не указывается, так как логарифм по любому основанию отличается от логарифма по основанию $2$ на константу.
$O(√n)$ Алгоритм с временной сложностью $O(√n)$ медленнее, чем $O(log\space n)$ , но быстрее, чем $O(n)$ . Пример — перебор делителей числа $n$ .
$O(n)$ Линейный алгоритм перебирает входные данные постоянное число раз. Зачастую это наилучшая возможная временная сложность в задачах, где на входе поступает n элементов, потому что обычно, чтобы получить ответ, необходимо обратиться к каждому элементу хотя бы один раз.
$O(n · log\space n)$ Такая временная сложность часто означает, что алгоритм сортирует входные данные, поскольку временная сложность эффективных алгоритмов сортировки равна $O(n · log\space n)$ . Есть и другая возможность – в алгоритме используется структура данных, для которой каждая операция занимает время $O(log\space n)$ .
$O(n^2)$ Квадратичный алгоритм нередко содержит два вложенных цикла. Перебрать все пары входных элементов можно за время $O(n^2)$ .
$O(n^3)$ Кубический алгоритм часто содержит три вложенных цикла. Все тройки входных элементов можно перебрать за время $O(n^3)$ .
$O(2^n)$ Такая временная сложность нередко указывает на то, что алгоритм перебирает все подмножества множества входных данных. Например, подмножествами множества {1, 2, 3} являются ∅ {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}
$O(n!)$ Такая временная сложность часто означает, что алгоритм перебирает все перестановки входных элементов. Например, перестановками множества {1, 2, 3} являются $(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)$

Алгоритм называется полиномиальным, если его временная сложность не выше $O(n^k)$ , где $k$ – константа. Все приведенные выше оценки временной сложности, кроме $O(2^n)$ и $O(n!)$ , полиномиальные. На практике константа $k$ обычно мала, поэтому полиномиальная временная сложность, грубо говоря, означает, что алгоритм может обрабатывать большие входные данные. Большинство алгоритмов в олимпиадном программировании полиномиальные. Однако существует много важных задач, для которых полиномиальный алгоритм неизвестен, т. е. никто не знает, как решить их эффективно. Важным классом задач, для которых неизвестен полиномиальный алгоритм, являются NP-трудные задачи.

Вычислив временную сложность алгоритма, мы можем еще до его реализации проверить, будет ли он достаточно эффективен для решения задачи. Отправной точкой для оценки является тот факт, что современный компьютер может выполнить несколько сотен миллионов простых операций в секунду. При всем при том важно помнить, что временная сложность – всего лишь оценка эффективности, поскольку она скрывает постоянные множители. Например, алгоритм с временной сложностью может выполнять как $n/2$ , так и $5 · n$ операций, а это существенно влияет на фактическое время работы.

Оценка временной сложности по размеру входных данных:

Размер входных данных	Ожидаемая временная сложность
n ≤ 10	$O(n!)$
n ≤ 20	$O(2^n)$
n ≤ 500	$O(n^3)$
n ≤ 5000	$O(n^2)$
n ≤ 106	$O(n・log\space n)$ или $O(n)$
n велико	$O(1)$ или $O(log\space n)$

Введение

Оглавление

Соревнования по программированию

Языковые средства (С++)

Ввод-вывод

Работа с числами

Представление целых чисел в компьютере

Выполнение арифметических действий над целыми числами в компьютере

Сокращение кода

Побитовые операции

Вычислительная сложность