Для оценки времени работы алгоритмов принято использовать O-нотацию. Она задает верхнюю асимптотическую сложность алгоритма. То есть, она показывает как, при прочих равных, изменяется время работы алгоритма при изменении размера входных данных. Например, если некоторый алгоритм имеет сложность O(n*n), то при увеличении размера входных данных в 3 раза, время его работы увеличится примерно в 9 (3*3) раз.

Ее же используют для сравнения эффективности алгоритмов. Так, если первый алгоритм имеет сложность O(n*n), а второй — O(n), то последний значительно быстрее первого. При увеличении размера входных данных в 3 раза, время работы первого алгоритма увеличится примерно в 9 раз, а второго — в три раза. Почему примерно?

Дело в том, что O-нотация не дает точных оценок сложности. Она дает лишь асимптотическую, то есть примерную оценку сложности. Если алгоритм имеет сложность O(n), то это значит, что время его работы с увеличением объёма входных данных растет не быстрее, чем линейная функция

k*n + b

где k и b — некоторые конечные числа. Причем O-нотация ничего не говорит о том, чему равны эти числа. Она говорит лишь о том, что они существуют. К чему это приводит?

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

2*n + 10

Время работы второго растет не быстрее функции:

1000*n + 215

Очевидно, что первый алгоритм значительно быстрее второго, но, с точки зрения O-нотации оба они имеют сложность O(n). Да, формально следовало бы записать O(2n) и O(1000n), но так обычно никто не делает. Для O-нотации главным фактором является асимптотика, а не точные значения коэффициентов. Тем более что в большинстве случаев их поиск — трудная задача. Повторюсь, главное — асимптотика. А она в обоих случаях — линейная. Поэтому и получаем O(n).

Для наглядности рассмотрим две задачи: вычисление среднего арифметического значения и среднеквадратического отклонения (СКО). Первая задача требует времени O(n), так как для её решения нужно пройтись по всему массиву чисел. Вторая задача требует времени O(2n), так как ей нужно дважды пройтись по всему массиву чисел. Первый раз для нахождения среднего арифметического, а второй раз для вычисления самого СКО. Однако, как я говорил ранее, точные значения коэффициентов никому не интересны. Поэтому оба этих алгоритма будут иметь сложность O(n). То есть, с точки зрения O-нотации, они будут иметь одинаковую сложность.

Другой пример: инкремент целого числа и вычисление квадратного корня. В обоих случаях объём входных данных не может изменяться (размер числа определяется архитектурой ЭВМ, а не пользователем алгоритма). Поэтому их сложность составит O(1). Однако очевидно, что инкремент целого числа выполняется значительно быстрее, чем расчет квадратного корня (если конечно речь не идет о какой-то супер узко-специализированной машине). Тем не менее, O-нотация нам об этом не расскажет.

Заключение

Цель данной статьи не сказать о том, что O-нотация — плоха и ее нужно менять. Нет, она хорошо справляется со своей задачей. Я лишь хотел обратить Ваше внимание на то, что она учитывает не всё. Она даёт лишь примерные (асимптотические) оценки сложности и не более того. Реальную сложность того или иного алгоритма Вы должны оценивать сами.