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

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

На промежутке (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, α ∈ ℝ ).

log_a (x₁ x₂) = log_a x₁ + log_a x₂, log a x 1 x 2 = log a x 1 — log a x 2 , log_a x α = α log_a 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.

АСВысший разум (145686) 10 лет назад
Посто и со вкусом. Мои позравления. У вас явно талант.
Евгений Кутузов Просветленный (49095) Спасибо, я польщён. 🙂
жора жораУченик (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) на маленьких числах.

Евгений КутузовПросветленный (49095) 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

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

пределы — Доказать предел

Мне говорили, что после того как перейдем к $% \lim_x^ \ x =0 $%, воспользоваться теоремой о композиции. что-то в таком роде. Это что?

задан 20 Окт ’14 21:52

Snaut
391 ● 1 ● 28 ● 82
65&#037 принятых

@Tiki_6O, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(21 Окт ’14 10:22) Виталина

1 ответ

Этот факт означает, что логарифм растёт медленнее любой степенной функции. Равноценный факт состоит в том, что экспонента (с показателем $%>1$%) растёт быстрее любой степени. Одно из другого выводится в обе стороны.

Начнём вот с какого факта: пусть $%a>1$%; положим $%a=1+\alpha$%. Тогда $%a^n=(1+\alpha)^n=1+n\alpha+\frac2\alpha^2+\cdots$%, где все остальные члены неотрицательны. Отсюда следует, что экспонента растёт быстрее квадратичной функции (коэффициент при $%n^2$% здесь положителен). Понятно, что такая квадратичная функция растёт быстрее линейной.

Это рассуждение доказывает, что $%\lim\limits_\frac=0$% при $%a>1$%. То же самое можно записать в виде $%n=o(a^n)$%, где $%n\to\infty$%. Отсюда легко распространить утверждение на случай функций вместо последовательностей: $%\lim\limits_\frac=0$%, или $%x=o(a^x)$% при $%x\to+\infty$%.

Теперь пусть $%k>0$%. Докажем, что $%x^k=o(a^x)$% при тех же условиях. Из $%a>1$% следует, что $%b=a^>1$%. Тогда $%\lim\limits_\frac=0$% по доказанному ранее. Тогда $%k$%-я степень также стремится к нулю, то есть $%\lim\limits_\frac=0$%. Теперь мы знаем, что $%x^k=o(a^x)$%: степень растёт медленнее экспоненты.

Теперь рассмотрим Ваш пример. Положим $%y=-\ln x$%, что стремится к $%+\infty$% когда $%x\to+0$%. При этом $%x=e^$% и $%x^=e^$%. При этом $%x^\ln x=-y/e^$%. Эта величина стремится к нулю по предыдущему — за счёт того, что $%a=e^ > 1$%. Тем самым, отношение величин $%\ln x$% и $%\frac1$% в пределе равно нулю, то есть $%\ln x=o(\frac1)$% при $%x\to+0$%.

отвечен 21 Окт ’14 0:55

falcao
300k ● 9 ● 38 ● 55

Вопрос по Главе 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
Регистрация: 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
Регистрация: 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
Регистрация: 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
Регистрация: 29.11.2014 — 19:08

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

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

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

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