Оценка сложности алгоритмов

Чтобы выполнить какой-либо алгоритм, компьютеру необходимо проделать определенное количество операций, и это количество ограничено. Оптимальное время работы алгоритма для любых входных данных на олимпиадах – $1$ секунда. Компьютер способен выполнить ограниченное количество операций за секунду (Python позволяет произвести примерно $10^6$ операций в секунду), это значит, что необходимо понимать, впишется ли ваше решение в ограничение по времени или нет.

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

Введем такое понятие, как $O$-большое. Говорят, что функция $f(n)$ является $O(g(n))$ (читается: $O$-большое от $g(n)$), если существует такая константа (постоянное значение) $C$ и $n_0$, что для всякого $n > n_0$ $f(n) \leq Cg(n)$.

В случае с алгоритмами мы рассматриваем в качестве возрастающей функции $g(n)$ входные данные, стремящиеся к бесконечности. Соответственно, $f(n)$ – асимтотическая сложность нашего алгоритма.

Рассмотрим программу:

    int N;
    cin >> N;
    cout << N + 1 << '\n';

Очевидно, что такая программа будет работать быстро. Вне зависимости от входных данных она будет выполняться за одно и то же количество операций. В таких случаях говорят, что программа работает за константу, а ее асимптотическая сложность – $O(1)$.

Но чаще всего сложность алгоритма напрямую зависит от входных данных. Например, в данной программе:

    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        someActions.here();
    }

цикл повторяется $N$ раз, соответственно, сложность ее работы – $O(N)$. Алгоритмы, сложность которых составляет $O(N)$, называются линейными.

Если мы встречаем двойной цикл:

    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            someActions.here();
        }
    }

то внутренний цикл повторяется $N$ раз по $N$. Таким образом, алгоритм работает за $O(N^2)$, его сложность квадратичная.

Ниже показан график зависимости времени выполнения от размера входных данных:

Вот примеры известных алгоритмов, имеющих такую асимптотику:

• $O(\log N)$ – бинарный поиск
• $O(\sqrt{N})$ – проветка числа на простоту
• $O(N)$ – линейные алгоритмы на массивах
• $O(N \log N)$ – продвинутые алгоритмы сортировки (merge sort и quick sort)
• $O(N^2)$ – алгоритмы на матрицах
• $O(N!)$ – перебор всех перестановок

Каждый раз при написании решения какой-либо задачи стоит задумываться над его асимптотической сложностью и обращать внимание на ограничения входных данных. Например, если входные данные могут возрастать до $10^9$, скорее всего, задача решается математически или применяются алгоритмы с логарифмической сложностью. А если входные данные могут быть не больше, чем $10^6$, то, скорее всего, стоит применить линейный алгоритм и т.д.