Упрощение формулы сложности

Нарисованная сложность в виде графика, где ось x — это размер входных данных n, а ось y — единицы времени, необходимые для обработки n элементов, выглядит следующим образом:

Мы уже можем видеть, что с увеличением количества элементов (ось X) время обработки быстро увеличивается: один элемент занимает 5 единиц времени, два элемента — 20 единиц, три элемента — 40 единиц и так далее.

Можем ли мы убрать некоторые части формулы, не слишком сильно изменяя этот график?

Очевидно, нужно определить весомую часть нашего алгоритма, которая оказывает наибольшее влияние на форму графика. Разделим формулу на составляющие:

Оранжевый график соответствует формуле 4*n^2, синий – n, а зеленый – n*log(n+1). Похоже, мы можем упростить формулу до 4*n^2 без радикального изменения формы графика.

Можно ли еще больше упростить нашу формулу? Уберем константный множитель 4:

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

Таким образом, для того, чтобы провести оценку, мы можем даже исключить константный фактор роста. Наша формула теперь сократилась до простого n^2, а ее форма все еще напоминает исходную кривую в полной формуле.

Теперь мы можем с уверенностью сказать, что нашему воображаемому коду требуется примерно n^2 единиц времени для обработки n элементов. Это гораздо проще, чем громоздкая формула, с которой мы начали!

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