Скорости роста функций

Графики четырех функций:

https://ggbm.at/GWhpSG98

Функция содержащая x², сначала растёт медленно, однако чем больше x, тем выше скорость роста функции. Скорость роста функций, содержащих x, постоянна всем интервале значений переменной. Функция 2logx вообще кажется постоянной, но это обман зрения. На самом деле она растёт, только очень медленно. Относительная высота значений функций также зависит от того, большие или маленькие значения переменной мы рассматриваем. Сравним значения функций при x = 2. Функцией с наименьшим значением в этой точке является x²/8, а с наибольшим - функция x+10. Однако с возрастанием x функция x²/8 становится и остаётся впоследствии наибольшей.

Некоторые часто встречающиеся классы роста функций:

	log2n	n	n log2n	n2	n3	2n

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

Быстрорастущие функции доминируют над функциями с более медленным ростом.

Каждый из классов Θ(f), Ω(f) и Ο(f) является множеством, и поэтому имеет смысл выражение "g - элемент этого множества". В анализе алгоритмов, однако, нередко пишут g = O(f), что на самом деле означает g ∈ O(f).