Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть О(следующая): 2lnn100, 20e,lnn!300,

Расположите следующие 5 функций в порядке увеличения скорости роста (каждая функция есть О(следующая): 2lnn100, 20e,lnn!300, 2lnn2, 22n10100 .

Говорят, что функция g мажорирует функцию f, если существует действительное положительное число k и целое положительное число m такое, что fn≤kgn
для всех n ≥m. Если g мажорирует f, то это обозначается как fn=О(gn).
Для того чтобы убедиться в справедливости fn=О(gn), существуют 2 строгих способа:
1) доказать, что начиная с некоторого n0 для всех больших значений n имеем fn ≤ с gn, где с -
некоторое положительное число.
2) обнаружить, что
limn→∞fngn<∞.
Второй способ надежен, если предел существует.
Функция 20e=consn, поэтому мы ее расположим первой (она вообще не растет).
Расположение заданных функций в порядке роста следующее: 20e, 2lnn2, 2lnn100, lnn!300, 22n10100.
Докажем это.
Функция 20e расположена первой, потому что она вообще не растет

.
Отметим, что для остальных функций находящиеся в них постоянные множители не играют никакой роли для определения скорости роста, поэтому мы их отбросим.
2lnn2<2lnn (в качестве с можно взять 1), 2lnn и 22n имеют одинаковое основание 2, поэтому
сравним их показатели:limn→∞lnn2n=limn→∞1n2nlnn(применено правило Лопиталя)=0.
Это означает, что 22n мажорирует 2lnn и, следовательно, 22n10100 мажорирует 2lnn2.
Следовательно, расположение функций 2lnn2, 2lnn100, 22n10100 в порядке роста следующее:
2lnn2, 2lnn100, 22n10100
Докажем, что lnn!300 мажорирует 2lnn . Для этого достаточно доказать, что
limn→∞2lnnlnn!<∞.
При вычислении пределов постоянные множители мы отбрасываем как не играющее никакой роли в установлении скорости роста функций