Вступление

Наверное, каждый из нас на начальных этапах сталкивался с ситуацией вида “я решил эту задачу, но она не проходит по времени”. Это может озадачивать: вы написали то, что от вас требовалось по условию, проверили свой код, но решение почему-то не укладывается в ограничение по времени (о котором вы раньше даже не задумывались). Причина этого явления проста: вы перешли с уровня задач на “реализацию” на уровень задач на “идею”. Это значит, что просто написать то, что сказано в условии, теперь недостаточно. Вам нужно начать задумываться об эффективности вашего решения.

В чём же выражается эффективность? Чаще всего самый важный параметр - время работы программы. Стоит сразу заметить, что в большинстве случаев время работы оптимального и наивного решения отличается далеко не в 2 раза. Наивное решение для многих задач может работать минуты, часы, года, а часто и вовсе астрономические величины. Причины такого поведения мы рассмотрим ниже.

Другим важным параметром является количество использованной памяти, но оно редко становится ключевым для эффективности программы. Если ваше решение не укладывается в ограничение по памяти, оно скорее всего не уложится и в ограничение по времени.

Пример задачи

В качестве примера рассмотрим следующую задачу:

Дан массив из \(N\) натуральных чисел (\(N \le 10^6\)). Числа не превышают \(10^6\). Сколько пар равных чисел в нём содержится?

Казалось бы, что может быть проще? Недолго думая вы пишете код такого вида:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;

int arr[MAX_N];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    long long ans = 0;

    for (int i = 0; i < n; i++) {           // внешний цикл
        for (int j = i + 1; j < n; j++) {   // внутренний цикл
            if (arr[i] == arr[j]) {
                ans++;
            }
        }
    }

    cout << ans << endl;
}

И получаете вердикт TL (Time Limit Exceeded). Давайте разберёмся, почему: посчитаем, сколько операций выполнит наш алгоритм в худшем случае (при \(N = 10^6\)). Рассмотрим первую итерацию внешнего цикла (\(i = 0\)). Во внутреннем цикле переменная \(j\) будет принимать по очереди все значения от \(1\) до \(N - 1\), то есть тело внутреннего цикла выполнится \(N - 1\) раз. На второй итерации внешнего цикла число итераций внутреннего будет равно \(N - 2\). На третьей \(N - 3\). И так далее, пока это число не достигнет нуля. Общее число итераций мы можем выразить следующей формулой:

\[(N - 1) + (N - 2) + \ldots + 1\]

Преобразуем её, используя формулу суммы арифметической прогрессии:

\[(N - 1) + (N - 2) + \ldots + 1 = \\ = 1 + 2 + \ldots + (N - 1) = \\ = \sum\limits_{i = 1}^{N - 1} i = \\ = {1 + (N - 1) \over 2} * (N - 1) = \\ = {N * (N - 1) \over 2}\]

В худшем случае это будет равно

\[{10^6 * (10^6 - 1) \over 2} = 499999500000 \approx 5 * 10^{11},\]

Или примерно пятьсот миллиардов. Много, не так ли? В 2017-м году обычный процессор может выполнять на одном ядре примерно \(10^8\) операций в секунду. Стоит заметить, что не все операции равнозначны. С \(10^8\) операций сложения любой процессор справится без проблем, а, например, взятия квадратного корня, уже не каждый. Принимая производительность процессора за \(10^8\) операций/секунду, наша программа выполнится за каких-то \(5000\) секунд, примерно \(1.5\) часа. Стоит ли говорить, что это неприемлемо?

Как же решать эту задачу? Нужно придумать алгоритм, который будет работать гораздо быстрее. В таких ситуациях всегда нужно внимательно проанализировать ограничения на входные данные. Кроме ограничения на размер массива, у нас также ограничены сами числа: они не превышают \(10^6\). Можно ли это как-либо использовать? Да.

Посчитаем вспомогательный массив \(c\), где \(c[i]\) - количество чисел \(i\) в изначальном массиве. Если в массиве пять троек, то \(c[3] = 5\). Как в таком случае получить количество пар троек? Владея элементарной комбинаторикой, или черновиком с ручкой, можно заметить, что количество всех пар связано с количеством элементов формулой

\[P = {x * (x - 1) \over 2}\]

Значит, мы можем найти количество пар троек:

\[P = {5 * 4 \over 2} = 10\]

Посчитаем этот параметр для всех чисел и сложим получившиеся результаты. Это и будет ответом на задачу.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int MAX_VALUE = 1000000;

int arr[MAX_N];

// Для чисел от 0 до 1000000.
// Мы будем умножать эти значения, поэтому используем тип long long
// для предотвращения переполнения.
long long num_count[MAX_VALUE + 1];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        num_count[arr[i]]++;
    }

    long long ans = 0;

    for (int i = 0; i <= MAX_VALUE; i++) {
        ans += num_count[i] * (num_count[i] - 1) / 2;
    }

    cout << ans << endl;
}

Как видите, мы уложились в два цикла, в худшем случае каждый из них выполнит по миллиону итераций, и общее число операций будет порядка \(3 * 10^6\). Значит, на том же процессоре наша программа будет выполняться за \(30\) мс, что уже гораздо лучше.

Асимптотическая сложность

На практике точно оценить время работы программы почти что невозможно. Даже если вы точно подсчитаете все элементарные операции (инструкции машинного кода) вашей программы, что уже неоправданно сложно, каждая инструкция выполняется процессором за разное количество тактов. Процессор часто выполняет несколько операций сложения за такт, а вот для операции деления требуется около десяти тактов. Время выполнения одного такта также может варьироваться (процессор не всегда работает на максимальной тактовой частоте). А если вспомнить про многопоточность и многоядерность, то перспективы окончательно омрачняются. Поэтому точным временем работы в информатике не оперируют.

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

В предыдущем разделе мы считали так называемое “примерное количество операций” наивного алгоритма. Посчитаем его ещё раз, в этот раз учитывая все операции, включая ввод-вывод и другие мелкие операции вне основных циклов, и выразим общее количество как функцию от размера массива \(N\):

\[Ops(N) = {N * (N - 1) \over 2} + N + c\]

Слагаемое \(N\) учитывает цикл для ввода массива, а \(c\) - некоторая константа, соответствующая количеству операций вне всех циклов. Преобразуем эту формулу в стандартный вид:

\[Ops(N) = {N^2 \over 2} - {N \over 2} + c\]

То есть, принимая, что время работы прямо пропорционально количеству операций, время работы наивного алгоритма равно:

\[T(N) \approx {N^2 \over 2} - {N \over 2} + c\]

Теперь необходимо ввести понятие “O большое”. “О большое” - математический способ приблизительной оценки функции. Запись выглядит следующим образом:

\[f(x) \in O(g(x))\]

И формально означает следующее утверждение:

Существуют такие числа \(M\) и \(C\), что выполняется утверждение: \(f(x) < C * g(x)\) для всех \(x > M\).

Или, проще говоря, для достаточно больших \(x\), \(f(x)\) растёт медленнее \(g(x)\).

Применив такую запись к нашему времени работы мы получим:

\[T(N) \in O(N^2)\]

Мы откинули члены \(N\) и \(c\), потому что при достаточно больших \(N\) они бесконечно малы по сравнению с \(N^2\). Деление на \(2\) откидывается, так как это, по сути, умножение на константу \({1 \over 2}\), а константа нас не интересует при оценке скорости роста.

Вообще, так как “О большое” ограничивает рост функции только сверху, с таким же успехом можно сказать, что \(T(N) \in O(N^3)\), или \(T(N) \in O(N^4)\). Но на практике ограничение стараются подобрать как можно точнее, так что записи выше в каком-то смысле можно назвать некорректными, так как очевидно, что существует более точное ограничение.

Строго говоря, у зависимости времени работы от входных данных есть собственное название. Этот параметр называется асимптотической сложностью, или просто сложностью. Можно сказать, что сложность рассматриваемого алгоритма \(O(N^2)\), или что у алгоритма квадратичная сложность. На практике понятия “время работы”, “сложность” и “асимптотика” используются как взаимозаменяемые.

Используя новые термины, можно сказать, что у наивного решения этой задачи сложность \(O(N^2)\), а у оптимального \(O(N)\).

Часто сложность решения нельзя выразить через одну переменную, в таких случаях можно использовать функции от нескольких переменных: \(O(MN)\), \(O(N \log M)\), и так далее.

Для одной переменной чаще всего встречаются следующие значения сложности алгоритма:

  • \(O(1)\)
  • \(O(\log N)\)
  • \(O(\log^2 N)\)
  • \(O(\sqrt[\leftroot{2} 3] N)\)
  • \(O(\sqrt N)\)
  • \(O(N)\)
  • \(O(N \log N)\)
  • \(O(N \log^2 N)\)
  • \(O(N \sqrt N)\)
  • \(O(N^2)\)
  • \(O(N^2 \log N)\)
  • \(O(N^3)\)
  • \(O(2^N)\)
  • \(O(N!)\)

Иногда нужно подчеркнуть, что несмотря на то, что два алгоритма имеют одинаковую сложность, один из них заметно эффективнее другого. В таких случаях говорят, что у такого алгоритма ниже константа.

Пессимистичная и средняя сложность

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

В таких ситуациях чаще всего используются “не совсем точные” определения сложности, которые не учитывают конкретной структуры входных данных. Это либо пессимистичная сложность (англ. worst-case complexity), либо средняя сложность (англ. average complexity). В олимпиадных задачах важнее первое из них, и под словом “сложность” понимают имеют пессимистичную сложность.

Определение достаточно интуитивно - если пессимистичная сложность алгоритма \(O(N^2)\), где \(N\) - размер входного массива, это значит что существует хотя бы один такой массив, для которого алгоритм работает за \(O(N^2)\). При этом не имеет значения, как быстро работает алгоритм в среднем случае, важен только худший.

Ограничение по времени и асимптотическая сложность

Сложность алгоритма - более фундаментальная и абстрактная величина, чем количество операций, и тем более чем абсолютное время работы. Тем не менее, при решении задач ограничение накладывается именно на абсолютное время: тестирующая система не может определять сложность вашего решения по его исходному коду и сравнивать её со сложностью авторского решения. В связи с этим возникает вопрос: как, оценив сложность решения, понять, помещается ли оно в ограничение по времени.

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

Метод банально прост: пусть сложность нашего решения \(O(f(Input))\). Посчитаем максимальное значение \(f(Input)\) для всех входных данных. Чаще всего оно будет равно значению функции \(f\) для максимальных значений всех её параметров. Пусть ограничение по времени в задаче равно \(t\) секунд. Рассмотрим значение \(\max{f} \over t\):

  • Если \({\max{f} \over t} \le 10^7\), то решение почти наверняка уложится в ограничение по времени.
  • Если \({\max{f} \over t} \ge 10^9\), то решение почти наверняка не уложится в ограничение по времени.
  • Если \(10^7 \le {\max{f} \over t} \le 10^9\), то точно сказать невозможно: зависит от конкретного алгоритма (константы). Как границу между “скорее подходящими” и “скорее неподходящими” решениями можно принять \(10^8\).

Чем сложнее и нестандартнее задача, тем выше вероятность того, что метод может оказаться неточным или вовсе ошибочным. Особенно это касается решений задач, сложность которых сложно точно определить.

Оценка используемой памяти

Кроме времени работы, при решении задач также играет роль количество использованной памяти. Его тоже можно оценивать, используя асимптотические ограничения вида \(M(N) \in O(N)\), однако на практике это используется гораздо реже.

Дело в том, что в отличие от времени работы, мы можем достаточно точно предсказать количество использованной памяти, глядя на исходный код решения. Для оценки используемой памяти чаще всего достаточно взглянуть на используемые контейнеры: массивы, вектора, std::set, std::map, и другие. Для каждого контейнера мы можем принять количество используемой им памяти равным \(N * (S + K)\), где \(N\) - максимальное возможное количество элементов контейнера за весь алгоритм, \(S\) - размер одного элемента контейнера (для int - 4 байта, double - 8 байт, и т.д.), а \(K\) - некоторая константа, специфическая для контейнера. Для массивов и векторов можем принять \(K\) равным нулю, а для более сложных структур - не более 32 байт.

Чаще всего при решении задач, требующих использования большого количества памяти, близкого к ограничению, подавляющую часть используемой памяти будут занимать именно многомерные массивы/вектора. Хорошим методом при оценке используемой памяти будет отнять около 50 МБ от ограничения, и посчитать, хватает ли оставшейся памяти для основных массивов. Например, при ограничении 256 МБ можно спокойно создавать массивы, в сумме занимающие не более 200 МБ памяти.

Разумеется, такой метод применим только тогда, когда зависимость используемой памяти от входных данных тривиальна, и все большие контейнеры глобальны или “почти глобальны” (создаются при любых входных данных). Для более сложных задач нужно сначала проанализировать, какие входные данные будут пессимистичными, то есть приведут к максимальному использованию памяти.