Что растет быстрее показательная или степенная функция
Перейти к содержимому

Что растет быстрее показательная или степенная функция

  • автор:

Учебник. Логарифмическая функция

На промежутке (0; +∞) определена функция, обратная к a x (a > 0, a ≠ 1). Эта функция называется логарифмической:

Логарифмическая функция непрерывна и строго возрастает (если основание a > 1) или строго убывает (если 0 < a < 1)на всей области определения. Множество её значений – все действительные числа.

Так как логарифмическая и показательная функции взаимно обратны, то при a > 0, a ≠ 1, a log a x = x , x > 0 log a a x = x , x ∈ ℝ .

Ниже приведены некоторые свойства логарифмов
(x > 0, x 1 > 0 , x 2 > 0 , a > 0, a ≠ 1, b > 0, b ≠ 1, α ∈ ℝ ).

loga (x1 x2) = loga x1 + loga x2, log a x 1 x 2 = log a x 1 — log a x 2 , loga x α = α loga x, log a x = log b x log b a , log a b = 1 log b a , log a α x = 1 α log a x , α ≠ 0.

Логарифм по основанию e называется натуральным и обозначается ln x. Логарифм по основанию 10 называется десятичным и обозначается lg x.

Сравнивая рост степенной, показательной и логарифмической функции при больших x, можно прийти к следующим выводам: lim x → + ∞ e x x n = + ∞ , n ∈ ℕ , lim x → + ∞ x n ln x = + ∞ , n ∈ ℕ .

Показательная функция растет быстрее степенной, а степенная – быстрее логарифмической.

Отметим также еще два важных предела: lim x → 0 ln 1 + x x = 1 , lim x → 0 e x — 1 x = 1 .

Алгебра. Какая функция возрастает быстрее: степенная или показательная? Почему?

Ну, например, вот почему:
Рассмотрим отношение f(x) / g(x). Если при x->+∞ оно растёт, то f возрастает быстрее, чем g. А если наоборот, то наоборот 🙂
Найдём производную отношения x^n / e^x.
(x^n / e^x)’ = (x^(n-1)) / (e^x(n-x))
Очевидно, что при x->+∞ знаменатель отрицателен, а числитель положителен.
Производная отрицательна, отношение убывает, => x^n возрастает медленнее e^x.

АСВысший разум (145683) 10 лет назад
Посто и со вкусом. Мои позравления. У вас явно талант.
Евгений Кутузов Просветленный (49105) Спасибо, я польщён. 🙂
жора жораУченик (112) 7 лет назад
Вы производную взяли не верно, прочтите ответ ниже.
Остальные ответы

Могу вас огорчить, Евгений Кутузов, но у вас нет таланта, вы не правильно взяли производную.
При взятии производной от частного функций нужно применять формулу (f/g)’=(f’*g-g’*f)/g^2
Если мы ее применим к нашему частному, то в ответе получим (f=x^n, где n — любое число ; g=e^x): (x^n/e^x)’=(n*x-x^n)/e^x
Чтобы сделать вывод о том возрастает или убывает наше частное функций, нужно вспомнить свойство: «функция возрастает, если ее производная положительна и наоборот ( в нашем случае обозначим частное новой функцией m=f/g)»
А это значит, что если производная функции m положительна, то возрастает быстрее степенная функция, если наоборот, то быстрее возрастает показательная.
Итог у вас тоже правильный, что на бесконечности (x->+∞) показательная функция возрастает быстрее.
В это можно убедиться, подставив конкретную степень и посчитав производную ((x^n/e^x)’=(n*x-x^n)/e^x) на маленьких числах.

Евгений КутузовПросветленный (49105) 7 лет назад

Да всё верно, зачем было столько писать-то. Достаточно было вот так:

«У вас опечатка: (n-x) стоит в знаменателе, а не в числителе. Производная равна (n — x) x^(n — 1) / e^x.
Что, впрочем, не влияет на общий вывод».

жора жора Ученик (112) нет, этого не достаточно потому что, я тоже ошибся, читайте ниже
жора жораУченик (112) 7 лет назад
Ребятушки, извините, я тоже ошибся.
Вот панацея:
(x^n/e^x)’=(n*x^(n-1)-x^n)/e^x

Евгений Кутузов Просветленный (49105) n*x^(n-1) — x^n = (n — x)x^(n — 1). Вы это сегодня увидите или нет? )

Виктор КомиссарУченик (193) 3 недели назад

Ребят, просто применяем правило Лопиталя, где lim(f(x)/g(x))=lim(f'(x)/g'(x)), при x->x0, и так далее, здесь можно это применить, функции дифференцируемы на всей действительной оси, непрерывна, а также неопределенность вида [бесконечность/бесконечность]
Используем это правило n раз для обращения степени в ноль и получим, так как e^x не меняется, lim(n!/e^x)=0, при x->+бесконечности, это говорит нам, что показательная функция «сильнее» чем степенная, а значит растет быстрее.
Можно и для общего вида доказать, там просто добавиться (lna)^n в делителе.

Научный форум dxdy

Факториал растёт быстрее любого многочлена. Как доказать?

На страницу Пред. 1 , 2 , 3 След.

Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 17:04

Заслуженный участник

atlakatl в сообщении #1072909 писал(а):
Это другой подход к доказательству?

$\frac<a_<n></p>
<p>Да, другой именно подход. Факториал растёт быстрее степени ровно потому же, почему быстрее степени растёт показательная функция: потому, что >>:\frac>>$» /> подпирается некоторой константой. И при этом в случае факториала эта подпорка гораздо грубее, чем в случае показательной.</p><div class='code-block code-block-5' style='margin: 8px 0; clear: both;'>
<!-- 5pocketpc -->
<script src=

А логарифмов на этот момент и вовсе нет. Скрипач не нужен.

Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 19:12

Заслуженный участник

Последний раз редактировалось provincialka 13.11.2015, 19:21, всего редактировалось 2 раз(а).

Недавно была похожая тема «Доказать равенство» . Как раз про показательную функцию. Собственно, тот метод можно применить и здесь.

$\sum\limits_<n=1></p>
<p>Собственно, идея простая: ряд ^<+\infty>\frac$» /> сходится по признаку Даламбера, значит, его общий член стремится к 0.</p>
<p><b>Re: Факториал растёт быстрее любого многочлена. Как доказать?</b><br />
13.11.2015, 19:38</p>
<table cellspacing= Заслуженный участник

provincialka в сообщении #1073066 писал(а):
идея простая: ряд

это не вполне спортивно: рядов на этот момент ещё нет. Хотя суть дела, разумеется, именно в этом.
Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 19:40

Заслуженный участник

ewert
Ну, шутка же!
Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 19:56

Заслуженный участник

provincialka в сообщении #1073069 писал(а):
Ну, шутка же!

ну так доцент — он же тупой
Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 20:30

Заслуженный участник

На меня намекаете?
Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 20:34

Заслуженный участник

это дело обоюдное, скорее всего
Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 22:11

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

Re: Факториал растёт быстрее любого многочлена. Как доказать?
13.11.2015, 22:24

Заслуженный участник

Это слишком на пальцах. Если бы этого хватало, тема, возможно, и не появилась бы.
Re: Факториал растёт быстрее любого многочлена. Как доказать?
14.11.2015, 06:56
Что значит слишком на пальцах? Где недостаток?
Re: Факториал растёт быстрее любого многочлена. Как доказать?
14.11.2015, 07:24

Заслуженный участник

levtsn в сообщении #1073114 писал(а):

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

levtsn в сообщении #1073220 писал(а):
Где недостаток?

Берём две последовательности $a_n=2^n$ и $b_n=2^n\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac14\right)\ldots\left(1-\frac1n\right).$
Последовательность $a_n$увеличивается в константу раз, а $b_n$— во всё возрастающее число раз. Следовательно последовательность $b_n$растёт быстрее последовательности $a_n$.

Вопрос по Главе 7. Задача про скорость роста функций

Аватар пользователя Ольга Исакова

Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
1) f1(n) = n!;
2) f2(n) = n2;
3) f3(n) = ln n ;
4) f4(n) = n(ln n).

  • 8269 просмотров

28 марта, 2016 — 08:43
Регистрация: 08.02.2016 — 14:58
29 марта, 2016 — 03:57
Регистрация: 15.01.2016 — 10:16

А поясните, пожалуйста, почему Вы так считаете? Спасибо

29 марта, 2016 — 08:11
Регистрация: 08.02.2016 — 14:58

1. Любой полилогарифм растет быстрее любого полинома. Значит, ln n=O(n). Следовательно, ln n=O(n (ln n)), т.к. n (ln n) растёт ещё быстрее, чем n.

2. Из ln n=O(n) также следует, что n(ln n)=O(n^2).

3. Факториал по скорости роста обгоняет даже показательную функцию, а любая показательная функция растёт быстрее полинома. Значит, n^2=O(n!). Можно ещё следующим образом показать, что факториал «больше» полинома. Чем выше степень полинома, тем он быстрее растёт. Например, n^2=O(n^3), n^3=O(n^5) и т.д. Представим факториал в виде произведения: n!=n*(n-1)*(n-2)*. *1. Если раскрыть первые 3 скобки, мы уже получим функцию, «не меньшую» чем n^3. Следовательно, т.к. n^2=O(n^3), то n^2=O(n!).

29 марта, 2016 — 08:41

Аватар пользователя sed.ekb1993

sed.ekb1993
Регистрация: 29.11.2014 — 19:08

Ольга, но ведь n * (ln n) растёт в n раз быстрее, чем ln n.

Кроме того, где сравнение функций ln n и n * (ln n) с функцией n!?

29 марта, 2016 — 09:17
Регистрация: 08.02.2016 — 14:58

Т.к. n^2=O(n!) и n*ln n=O(n^2), то n*ln n=O(n!).

Т.к. n*ln n=O(n!) и ln n=O(n*ln n), то ln n=O(n!).

Отношение «расти быстрее» транзитивно, поэтому сравнивать функции, которые «меньше» n^2, с факториалом особого смысла нет.

По поводу первого замечания: n * (ln n) действительно растет быстрее, чем ln n. Только я не поняла, к чему данное замечание относилось. Поясните, пожалуйста.

29 марта, 2016 — 09:44

Аватар пользователя sed.ekb1993

sed.ekb1993
Регистрация: 29.11.2014 — 19:08

Значит, в Вашем первом ответе опечатка,

А по условиям задачи мы умеем следующее:

Следовательно, в Вашем ответе функция ln n растёт быстрее, чем n(ln n).

А про факториал, поправьте пожалуйста, если не прав, я читал, что это самая быстро растущая функция.

29 марта, 2016 — 10:35
Регистрация: 08.02.2016 — 14:58

В моём ответе всё верно. В задании просят расположить функции в порядке увеличения скорости роста, т.е. ln n, n*ln n, n^2, n!, или f3, f4, f2, f1.

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

29 марта, 2016 — 10:53
Регистрация: 08.02.2016 — 14:58

Поправка: в данном случае речь идёт о множестве не действительных чисел, а натуральных.

29 марта, 2016 — 11:13

Аватар пользователя sed.ekb1993

sed.ekb1993
Регистрация: 29.11.2014 — 19:08
29 марта, 2016 — 11:43
Регистрация: 02.02.2016 — 16:14
29 марта, 2016 — 12:11
Регистрация: 02.02.2016 — 16:14

Другое дело, что скорость роста n! не слишком хороша для сравнения, и не очень понятно, где ее можно использовать. Удобнее пользоваться показательной функцией (экспонентой).

29 марта, 2016 — 12:37
Регистрация: 08.02.2016 — 14:58

Извините, для какого сравнения не слишком хороша скорость роста факториала?

29 марта, 2016 — 13:27

Аватар пользователя sed.ekb1993

sed.ekb1993
Регистрация: 29.11.2014 — 19:08

Тут я ошибся, переклинило и я решал обратную задачу, вот и всё. выше про это уже извинялся.

29 марта, 2016 — 13:33

Аватар пользователя sed.ekb1993

sed.ekb1993
Регистрация: 29.11.2014 — 19:08

EugenO, не согласен, мы же смотрим не значения в точках, а скорость роста функции.

Или же, поясните подробнее, в чём именно на Ваш взгляд выражено это не удобство в сравнении.

30 марта, 2016 — 09:07
Регистрация: 02.02.2016 — 16:14

Для меня удобство экспоненты в том, что она очень хороша для анализа. Она легко представима в виде a^x, элементарно дифференцируема (скорость роста) и интегрируема, причем многократно, связана со вторым замечательным пределом, кроме того, интуитивно (для меня) понятна, я ее график много раз рисовал в детстве и с удовольствием ассоциирую с всевозможными процессами, происходящими в реальной жизни, поэтому вижу естественным применение в асимптотике. В то же время не смогу указать ни одного естественного инерционного процесса, который изменялся бы «со скоростью выше экспоненциальной». Кстати, известна Stirling’s approximation для оценки факториала, а оценки экспоненты через факториал что-то не припомню (наверное, в ней смысла нет).

30 марта, 2016 — 09:48
Регистрация: 08.02.2016 — 14:58

Хотелось бы узнать, зачем при анализе сложности алгоритмов Вы дифференцируете, интегрируете (причем многократно) экспоненту, как используете второй замечательный предел и формулу Стирлинга. Я не отрицаю, что, возможно, в теории сложности вычислений без этого нельзя обойтись. К сожалению, в данной области у меня очень скромный опыт((. А Вы, наверное, в этом вопросе отлично разбираетесь (может, даже на профессиональном уровне!). Поэтому очень интересно посмотреть, как применяет математический, комплексный и функциональный анализы в асимптотике настоящий специалист. Приведите, пожалуйста, пример.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *