Обозначение Big-O: сравнение

Различные характеристики этих классов временной сложности становятся очевидными, когда мы помещаем все эти функции на один рисунок:

Примечание: n заменено на x на следующих двух рисунках, так как инструмент построения графиков не позволяет мне указывать n вместо x в формулах.

Здесь сразу видно, как расходится время вычислений между разными классами сложности.

Графики O(n^2) и O(2^n) выглядят так, как будто они движутся очень близко друг к другу, однако после масштабирования оси Y до [0-200] разница становится очевидной.

Тебе покажется, что это похоже на разницу между графиками 4*n^2 и n^2, где разница не имеет значения. И теперь с этим почти идентичным графиком мы утверждаем, что разница имеет значение. Рассмотрим этот случай более подробнее.

Представь, что мы можем ускорить алгоритм O(n^2) на любой постоянный коэффициент m. Кривая будет становиться все более и более плоской с увеличением значения m, как показано на следующем графике.

Черная линия — полиномиальная функция n^2, зеленая линия — экспоненциальная функция 2^n, а красная и синяя — экспоненциальные функции, умноженные на коэффициент 0,5 и 0,1 соответственно. Синяя выглядит намного лучше, чем полиномиальная кривая. Так может ли O(2^n) победить O(n^2) только линейным ускорением?

Да и нет. При малых значениях n это действительно может произойти. Однако помните, что мы хотим выяснить, как ведет себя алгоритм, когда входные данные становятся все больше и больше. Итак, давайте масштабируем график, чтобы увидеть, как кривые ведут себя при больших значениях n:

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