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

Очень часто важнейшей характеристикой той или иной зависимости является скорость ее роста. Есть даже целое направление в математике: асимптотические методы. Асимптотика — это и есть поведение на бесконечности (или вообще в пределе).

Итак, эталоном служит линейный рост, или рост линейных функций: y=ax. Можно и ax+b, но свободный коэффициент погоды не делает при больших х. Конечно, чем больше угловой коэффициент а, тем быстрее растет функция, но все равно рост считается линейным.

Дело в том, что есть функции, растущие быстрее любой линейной. Например, это степени xᵐ при m>1. Линейные функции попадают в этот класс при m=1, кстати. Степень обгонит любую линейную функцию, рано или поздно.

Но вот что любопытно! Есть линейная функция ax, есть степень xᵐ; и при любом m она обгонит линейную с любым a.

То есть показатель m роста степенной функции идет после всех показателей a роста линейной: похоже на трансфинитные числа.

Иными словами, идет ряд показателей скорости роста а от 1 до бесконечности для линейных, а после него идут показатели скорости роста для степеней от 1 до бесконечности. И никак до этого второго континуума не добраться, идя по первому.

Есть функции, растущие быстрее любой степени. Например, экспонента exp(kx), и у нее свой показатель скорости роста k.

И так далее.

Ладно. Ничего удивительного, что между двумя линейными есть множество линейных, растущих быстрее одной, но медленнее другой. И аналогично для степеней. Но удивительно, что есть функции, растущие быстрее данной линейной (с коэффициентом а), но медленнее любой другой линейной (с коэффициентом больше а)! И аналогично для всех других классов.

В самом деле, функция xln(x) растет быстрее, чем х, но медленнее, чем ax при любом a>1. Если попытаться описать скорость роста числом, то у ax это а, а вот у xln(x) этот показатель (гипотетический, конечно) больше единицы, но меньше любого другого числа a>1.

Как вам такое?

Если как-то легализовать эти показатели (числами их пока называть нельзя), то получается, что есть множество “чисел”, больших единицы, но меньших любого другого числа а>1. Причем они неархимедовы: можно таких “чисел” сколько угодно сложить, но сумма все равно будет такой же (больше 1, но меньше любого а<1). Потому что, например, ax при любом a уступает в скорости роста любой степени и тем более экспоненте. Так что axexp(x) растет быстрее экспоненты exp(x), но медленнее любой exp(kx) при k>1.

Можно сказать “ну что за дичь, нет таких чисел!”. Верно, их нет на числовой прямой. Но их можно ввести некоторыми дополнительными аксиомами. Так получается нестандартный анализ.

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

Разумеется, скорость роста функций здесь просто наводящее соображение.

Правда, как в том анекдоте: “пришла полиция и разогнала всех”: есть функции вроде 1/x, которые вырастают до бесконечности на конечном интервале и уделывают по скорости все экспоненты и вообще всё, что идет после них по нашей шкале роста.

Аналогично можно говорить о скорости убывания. И вот тут есть интересные нюансы в теории рядов. Известно, что для сходимости ряда необходимо, чтобы “общий член” стремился к нулю. Но не достаточно, пример Σ(1/n) — этот “гармонический” ряд расходится. То есть 1/n убывает недостаточно быстро, так что их сумма растет до бесконечности (скорость роста логарифмическая, как ln(n)). Но вот если n в знаменателе будет в любой степени s>1, то ряд сходится. Его сумма зависит от показателя степени s и называется ζ-функцией Римана. Да, эта та самая дзета. Да, и та самая тоже.

О ней в другой раз, а пока посмотрим, что будет, если заменить n в знаменателе на nln(n). Этот ряд расходится, что легко установить через интегральный признак (о нем тоже в другой раз), то есть скорость убывания недостаточно большая. А скорость роста суммы получается ln(ln(n)), что не просто медленно — невообразимо медленно. Логарифмы все пропорциональны друг другу, скорость роста у них можно считать одинаковой, так что заменим натуральный логарифм десятичным. Логарифм растет, мягко говоря, очень медленно: lg(10)=1, lg(100)=2, lg(1000000)=6, в общем, сколько нулей — такой и логарифм. Число “10 в степени 100” намного больше числа частиц в (видимой) Вселенной. Критическую плотность мы знаем, радиус видимой Вселенной тоже, можем оценить массу: она имеет порядок “10 в степени 53” килограмм. Грамм на три порядка больше: получим степень 56. Если это все водород, то надо умножить на число Авогадро (порядок 24), чтобы получить число атомов. Будет порядок 78. Как-то так. Число фотонов оценивают как порядок 84.

Так вот функция lglg(n) на числе 10 в степени 100 дает всего лишь 2. Но растет до бесконечности, в теории.

Функции вроде логарифма иногда называют “почти ограниченными”. Эта же ограничена в любом разумном смысле… кроме строго формального.

Так и живем.

Я уже рассказывал о том, как такие запредельные значения могут аукнуться. Например, в Санкт-Петербургском парадоксе мы бросаем монетку, пока не выпадет решка. Выпала впервые на n-ом броске — получаешь выплату в 2ⁿ монет. Хорошая игра, но сколько стоит платить за право сыграть один раз? Надо посчитать математическое ожидание, которое равно сумме всех мыслимых выплат, умноженных на их вероятности. Выпасть решка может впервые на любом броске n, вероятность этого события равна 1/2ⁿ и в точности обратна выплате. Так что вклад каждого исхода равен одной монете. Получается бесконечный средний выигрыш, что и составляет парадокс. Отсечка выплат на значении 2ᴺ (пусть и астрономически большом, например, 2¹⁰⁰) сразу дает вменяемый средний выигрыш в N+1 (например, 101).

Причем если у заведения нет таких денег, а есть тысяча рублей только, то и плата рубей в 10-11 разумна: не больше.

Или, скажем, первая заметка моего канала, про плюс-минус 10%. Если мы с равными шансами увеличиваем вложения на 10% или теряем те же 10%, то в среднем, теоретически, мы при своих. Хотя на практике все проиграем почти наверняка. Разницу между правильной теорией и (тоже правильной) практикой и обеспечивают теоретически возможные, но практически не встречающиеся исходы вроде “выиграть сто раз подряд”. Это маловероятно, но зато очень-очень доходно. Вклад такого исхода заметен. Хотя сам исход слишком маловероятен, чтобы его засчитывать. А парный к нему “сто раз проиграть” практически не отличается от “20 раз проиграть”, так и так это уже разорение, нуль есть нуль, как его не уменьшай, он нулем и останется. Поэтому теоретические “удачные” исходы вклад вносят, а неудачные — нет. Вот и получается среднее в теории равно начальному капиталу, а на практике убывает.

Нетрудно придумать пример, при котором среднее будет расти, и получается, что надо играть, а играть-то и не надо. Совсем крайний пример такой: с равными шансами капитал умножается на 4 или обнуляется. Каждый раз выгодно продолжать, ведь либо получишь 4, либо 0, равновероятно, то есть в среднем это 2. Но продолжать — это путь к разорению, причем довольно быстро. Здесь исход предопределен с вероятностью единица, но редкие события типа “выиграл семь раз подряд и увеличил капитал более чем в сто раз! А потом не повезло!” подводят теоретическую базу под продолжение игры. И нет хорошего критерия, когда надо “соскакивать”.

Ну и последнее. Есть такие ряды Фурье: если упрощать, то это разложение сигналов по гармоникам разных частот. Так вот, чем быстрее убывают коэффициенты ряда (вклады высоких частот), тем более гладкий сигнал. Убывать они могут сколь угодно медленно, и сигнал будет сколь угодно плох. Обобщенные функции тоже можно раскладывать в ряд Фурье, но для них коэффициенты могут не убывать. Так, для дельта-функции они постоянны. Могут и расти, и чем быстрее, тем “хуже” обобщенная функция. Однако рост коэффициентов не более чем степенной! На этом основана необратимость теплопроводности и диффузии: вперед можно считать с любого распределения, даже обобщенного, а вот назад — только с результата расчета вперед.

Впрочем, это тема для другой беседы. Да и о рядах Фурье в другой раз расскажу — есть что.

Вообщем, нашел в интернете описание скорости функций:
Оригинал:

Do you want the value to grow slow at first, but fast later? Use a polynomial or exponential function.
Do you want the value to grow fast at first, and slow down later? Use an nth-root or logarithmic function.

Перевод:

SQRT(x) и логарифмическая вначале растут быстро, но потом замедляются.
Степенные и показательные функции сначала растут медленно, потом ускоряются.

Захотелось как-то доказать эти утверждения, но не знаю как именно. Основная идея это смотреть на вторую производную, но вот не знаю как оценить. Взять, к примеру y = -x^2, y”= -2. Это говорит, о том, что скорость производной все время уменьшается, но сама эта функция будет (-inf;0) – возрастающей, (0;inf) – убывающей.
С корнем дела обстоят тоже не очень, там вторая производная равна (-1/4) * x^(-1,5). Что показывает, что это возрастающая функция, причем при бесконечности, она стремится к нулю. А вот как доказать, что она вначале резко возрастает….

8

3.1. Размер задачи. Скорость роста

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

а)
при проверке, будет ли заданное число
простым или составным, характерным
является само число,

б)
при поиске максимального элемента
массива – длина массива.

При
вводе в ЭВМ исходные данные кодируются
каким–либо способом. Числовые данные
обычно представляют в позиционных
системах счисления. Символьная информация
задаётся в стандартных кодах либо в
специальном графическом представлении.

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

Размером
задачи называют
длину последовательности символов, в
которой закодированы все исходные
данные.

Для
ЭВМ размер памяти обычно оценивается
числом байтов – последовательностей
из восьми бинарных разрядов.

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

Рассмотрим
на множестве натуральных чисел N
функции f(n)
и g(n).

1.
Функции g(n)
и f(n)
имеют одинаковую
скорость роста,
если при всех достаточно больших n,
начиная с некоторого n₀,
выполняется условие:

С₁
f(n)
≤ g(n)≤
С₂ f(n),
где С₁>0,С₂>0
– некоторые
константы.

2.
Скорость роста функции g(n)
больше
скорости
роста функции f(n),
если для любой сколь угодно большой
константы С
существует
некоторое n₀,
начиная с которого выполняется условие:

С
f(n)
≤ g(n).

3.
Скорость роста функции g(n)
ограничена
снизу скоростью
роста функции f(n),
если при всех
достаточно больших n,
начиная с некоторого n₀,
выполняется:

С
f(n)
≤ g(n),
где С
– константа.

4.
Скорость роста функции g(n)
ограничена
сверху
скоростью роста
функции f(n),
если при всех
достаточно больших n,
начиная с некоторого n₀,
выполняется условие:

g(n)
≤ С
f(n),
где
С –
константа.

Данное
определение позволяет сравнивать между
собой скорости роста функций достаточно
произвольного вида – как имеющих, так
и не имеющих предел отношения g(n)/f(n)
при n

.

Замечание.
Если скорость роста функции g(n)
равна скорости
роста функции f(n),
то скорость роста f(n)
ограничивает скорость роста g(n)
и сверху и снизу.

Пример
1. Рассмотрим
задачу с характерным параметром n,
у которой входными данными являются
все простые делители числа
n,
не равные единице. С увеличением n
число делителей k(n)
будет постоянно
изменяться в пределах от 1
(у простого числа) до log₂n
(у степеней
2).
Поэтому для длины входа k(n)
не существует
элементарной монотонной функции с
одинаковой скоростью роста. Для неё
можно только лишь указать ограничения,
верные при любых n:
1≤
k(n)
≤ log₂n.

В
общем случае для каждой положительной
функции натурального параметра k(n)
возможны следующие варианты:

1)
не существует монотонной функции f(n)
со скоростью
роста, равной k(n),
но при всех n,
начиная с некоторого n₀,
возможны лишь оценки:

C_н
f_н(n)
≤ k(n)
≤ C_в
f_в(n),

где
C_н>0,
C_в>0
– нижняя и
верхняя константы, f_н(n),
f_в(n)
–
различные функции.

2)
существует монотонная
функция f(n),
имеющая одинаковую скорость роста с
k(n),
для которой по определению при всех n,
начиная с некоторого n₀,
выполняется:

C_н
f(n)
≤ k(n)
≤ C_в
f(n),

где
C_н,
C_в
– константы,

В
варианте 2) предел отношения k(n)/f(n)
при n

может:

а)
не существовать и

б)
существовать, при этом:

Случай
2 б) является наиболее распространенным
при анализе скорости роста реальных
функций натурального параметра. Константу
С_р
в приведенном
выше пределе назовем константой
скорости роста,
а соответствующую скорость роста –
устойчивой.

Функции
g(n),
зависящие от натурального параметра
n,
могут иметь любой вид, однако скорости
их роста f(n)

для большей наглядности и упрощения
сравнений выражают через модельные
элементарные функции (логарифмы,
степенные, показательные и др) либо их
произведения. Наиболее часто используют
степенные функции n^α.
При
α
= 1 скорость роста функции n^α
называют линейной,
при α
=
2
– квадратичной,
при α
=3 – кубической
и
т.д. Все скорости роста вида n^α
называют полиномиальными.
С увеличением показателя α
полиномиальная скорость роста также
возрастает.

Существуют
функции, скорости роста которых
превосходят при n→
∞
любую
(со сколь угодно большим показателем
α)
полиномиальную скорость. Например,
2ⁿ,
еⁿ,
n!.
Скорости такого типа называют
экспоненциальными.

Из
двух функций g₁(n),
g₂(n)
с одинаковой устойчивой скоростью роста
f(n)
меньшие значения в пределе будет иметь
функция с меньшей константой скорости
роста С_р.

Пример
2.
Определить скорость роста f(n)
функции
g₁(n)=(n–5)/3,
константу скорости роста С_р,
а также определить пороговое значение
параметра n₀
и
константы С₁
, С₂,
при которых справедливо соотношение:
С₁
f(n)
≤
g(n)
≤
С₂
f(n).

Решение.
Так как при n
предел
отношения g₁(n)/n
существует и равен 1/3,
то скорость роста функции g₁(n)
равна
линейной полиномиальной f(n)=n¹,
а константа скорости роста С_р
=1/3.

Определим
параметры n₀,
С₁,
С₂.
Для этого используем следующие соотношения
:

(1/6)
n
¹

(n–5)/3

(1/3)

n
¹.

Правое
неравенство очевидно и выполняется при
любых n,
константа (1/6)
в левой части задана произвольно из
условия (1/6)
< (1/3),
величину n₀
определим из левого неравенства:

(1/6)
n¹

(n
–
5)/3

3
n

6
n
–
30

3
n

30
n

10.

Ответ:
f(n)=n¹,
С_р
=1/3,
n₀
=10,

С₁
= 1/6,
С₂
=1/3.

Пример
3.
Определить скорость роста f(n)
функции
g₂(n)=0,25(n–1)(n+2),
константу скорости роста С_р,
а также определить пороговое значение
параметра n₀
,
нижнюю
и верхнюю константы С₁
, С₂
, при которых справедливо соотношение
С₁
f(n)≤
g(n)
≤
С₂
f(n).

Решение.
При n
предел
отношения
g₂(n)/n²
существует
и равен 1/4.
Следовательно, скорость роста функции
g₂(n)
равна
квадратичной полиномиальной f(n)=n²,
С_р
=1/4.

Определим
n₀
,
С₁
, С₂
. Для этого используем соотношение

n²/4

0,25(n–1)(n+2)

n²/3.

Определим
граничное значение n₀,
начиная с которого будут выполняться
неравенства в левой и правой частях.

Левая
часть:

n²/4

0,25
(n–1)(n+2)
n²
n²+n
–2

n

2

n₀
=2.

Правая
часть:

0,25(n–1)(n+2)
n²/3
3n²+3n–6

4n²

n²–3n+6

0.

Так
как дискриминант уравнения отрицательный,
то данное неравенство справедливо при
любых
n.

Ответ:
f(n)=n²,
С_р
=1/4,
n₀
=2,

С₁
= 1/4,
С₂
=1/3.

Обозначим
скорость роста размера задачи через
r(n).
Рассмотрим примеры её определения.

Пример
4.
При проверке, будет ли число
n
простым или составным, r(n)
задачи определяется длиной записи
самого числа n.
В позиционной системе с основанием р

число бит, в записи числа
n
равно
]log_р
n[,
а размер задачи в байтах r(n)=]log_р
n[/8.

Пример
5. Задача
коммивояжера (ЗК). Задано n
упорядоченных населенных пунктов
{vⁿ}={v₁,
v₂,
… , v_n}.
Все расстояния между ними известны и
заданы симметричной матрицей стоимости
С
размером n

n,
элементы которой удовлетворяют
неравенству треугольника, т.е. при любых
i, j, k,
лежащих в пределах 1≤
i,
j,
k
≤
n,
справедливы соотношения: с
_i
j =
с
_j
i ;

с
_i
j +
с _j
k
≥ с
_i
k
.

Коммивояжеру
требуется выбрать из всего множества
циклических обходов {О
(vⁿ
)}
пунктов {vⁿ},
такой обход Оⁿ_опт,
у которого общая длина

_n-1

L(Оⁿ_опт)=
∑
с
_{i
j, i (j+1)}

+
с
_{i
n, i 1}

^j=1

будет
минимально возможной.

В
задаче изо всех исходных данных наиболее
быстро (n²)
растёт число элементов симметричной
матрицы стоимости С
размером nn.
Поэтому скорость роста размера данной
задачи будет квадратичной полиномиальной
–

r(n)=
n².

Вопросы
для проверки знаний.

1.
Что называют размером задачи и в каких
единицах ее измеряют в ЭВМ ?

2.
Что означает, что функции g(n)
и
f(n)
имеют
одинаковую скорость роста ?

3.
Что означает, что скорость роста одной
функции больше
скорости
роста другой функции ?

4.
Что означает, что скорость роста функции
g(n)
ограничена снизу
скоростью
роста функции f(n)
?

5.
Могут ли значения функции g(n),
у которой скорость роста ограничена
сверху
скоростью роста
функции f(n),
превышать значения данной функции ?

6.
В каком случае скорость роста функции
называют устойчивой и что называют
константой скорости роста ?

7.
Какие скорости роста функций называют
полиномиальными, линейными, квадратными
и кубическими ?

8.
Какие скорости роста функций называют
экспоненциальными ?

Практические
задания.

1.
Определить постоянную скорость роста
f(n)
функции
g(n)
=5(n-1)(n+3)/(n+5),
константу скорости роста С_р
,
а также найти значения n₀
,
С₁
, С₂
, при которых справедливо соотношение
С₁
f(n)
≤
g(n)
≤ С₂
f(n).

2.
Найти скорость роста f(n)
и
константы скорости роста С_р
функций:

а)
g₁(n)=0,1
(n!
–
2n²+
3n+
10)/(3n–1);

б)
g₂(n)=(еⁿ+
3n¹⁰+
7)(4n³
-6n²
+ 2n
+ 5);

в)
g₃(n)=
2ⁿ+
n
ⁿ
–
n²
.

3.
Доказать, что:

а)
скорость роста функции n!
превосходит в пределе при n→∞
скорость
роста функции 2ⁿ
;

б)
скорость роста функции 2ⁿ

превосходит в пределе при n→
∞
любую
(со сколь угодно большим показателем
α)
скорость роста полиномиальной функции
n^α
.

4.
Выяснить для функции скорости роста
f(n)
= n²(1+(–1)ⁿ)
+
2n+1:

а)
устойчивость скорости роста,

б)
ограниченность снизу,

в)
ограниченность сверху.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Public user contributions licensed under
cc-wiki license with attribution required

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