Сложность определяется как O(f(n)) («О большое от …») где f(n) — функция сложности. Это обозначение говорит о том, что при увеличении входных параметров (n) время работы алгоритма будет увеличиваться не быстрее чем f(n).

Так как это лишь оценочное представление, то не важны возможные константы, не зависящие от входных параметров т.е. O(n) = O(2*n) = O(n+10) и т.д. При этом возможна ситуация, когда сложность равна O(1). Это значит, что алгоритм работает константное время вне зависимости от размера входных данных. Рассмотрим это все на примерах.

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

Снова рассмотрим массив длиной N. Теперь мы хотим его отсортировать самым простым способом — пузырьком. Этот алгоритм подразумевает, что последовательно, один за одним, самые большие числа «выталкиваются» наверх, как пузырьки в воде. Для этого необходимо N раз пройтись по всем элементам, попарно их сравнить со следующим и поменять местами если один больше другого. Примерное количество операций при этом N*N = N^2. Сложность такого алгоритма квадратичная и выражается как O(N^2).

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

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