Общее (программирование)

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

Говорят, что если оценка есть $O(n),$ или $O(n^2),$ или … $O(n^a),$ где $a$ $-$ константа, то алгоритм называется полиномиальным (если показатель степени $n$ небольшой, то ещё и называется эффективным).

Ну, например, простейшая сортировка массива методом выбора имеет сложность $O(n^2).$ (Православные сортировки имеют сложность $O(n\times \log (n)).$) Что это означает? Что если мы будем увеличивать длину входа в $n$ раз, то количество операций, выполняемых компьютером, будет увеличиваться в $C\times n^2$ раз, где $C$ $-$ некая константа. Например, если увеличить $n$ в 5, 10, 20, 30, 40 раз, а $C=2,$ то количество операций будет увеличиваться в $2\times 5^2=50,$ $2\times 10^2=200,$ $2\times 20^2=800,$ $2\times 30^2=1800,$ $2\times 40^2=3200$ раз.

А вот если алгоритм имеет сложность $O(2^n),$ или вместо 2 любое другое константное основание, то его называют экспоненциальным (пример $-$ любой переборный алгоритм). Тогда, даже если $C=0.5,$ то при увеличении длины входа в 5, 10, 20, 30, 40 раз количество операций будет увеличиваться соответственно в $0.5\times 25=16,$ $0.5\times 2^{10}=512,$ $0.5\times 2^{20}=524288,$ $0.5\times 2^{30}=536870912,$ $0.5\times 2^{40}=549755813888$ раз. Что называется, почувствуйте разницу. Теперь, что такое вообще длина входа и количество операций, в чём их мерить? $n$ $-$ это биты, символы или количество строк? А количество операций $-$ это ассемблерные команды, количество шагов Машины Тьюринга, операторы C или что-то ещё? А вот в том-то и дело, что неважно, ведь у нас оценка не абсолютная, а асимптотическая, нам важно лишь, как меняется относительная скорость работы алгоритма по сравнению с относительным изменением количества входных данных, поэтому все эти конкретные коэффициенты попадут в это $O.$ Главное, какие команды мы обзовём элементарными. Ясно, что какой-нибудь метод list.sort() не тянет на элементарную. Как получить эту оценку? Правильный ответ $-$ подумать головой. И решить задачку: во сколько раз увеличится количество операций при увеличении длины входа в 10, 20, 30, 40 раз? и увидеть эту функцию $f(n).$ Иногда придётся доказать теорему. На практике обращают внимание на количество итераций циклов, на уровень вложенности циклов, и на вызовы функций, зависящих от n. Простой цикл for (int i = 0; i < n; i++) {...} (Си) даёт оценку $O(n),$ двойной цикл for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {...} (Си) уже $O(n^2),$ если их тела тривиальны и не зависят от $n.$ Если в теле циклов вызываются функции, которые сами по себе тоже зависят от $n,$ то это добавляет сложности и это тоже надо учитывать.