Вопрос по Главе 7. Задача про скорость роста функций
Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
1) f1(n) = n!;
2) f2(n) = n2;
3) f3(n) = ln n ;
4) f4(n) = n(ln n).
А поясните, пожалуйста, почему Вы так считаете? Спасибо
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!).
Ольга, но ведь n * (ln n) растёт в n раз быстрее, чем ln n.
Кроме того, где сравнение функций ln n и n * (ln n) с функцией n!?
Т.к. 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. Только я не поняла, к чему данное замечание относилось. Поясните, пожалуйста.
Значит, в Вашем первом ответе опечатка,
А по условиям задачи мы умеем следующее:
Следовательно, в Вашем ответе функция ln n растёт быстрее, чем n(ln n).
А про факториал, поправьте пожалуйста, если не прав, я читал, что это самая быстро растущая функция.
В моём ответе всё верно. В задании просят расположить функции в порядке увеличения скорости роста, т.е. ln n, n*ln n, n^2, n!, или f3, f4, f2, f1.
Поправка: в данном случае речь идёт о множестве не действительных чисел, а натуральных.
Другое дело, что скорость роста n! не слишком хороша для сравнения, и не очень понятно, где ее можно использовать. Удобнее пользоваться показательной функцией (экспонентой).
Извините, для какого сравнения не слишком хороша скорость роста факториала?
Тут я ошибся, переклинило и я решал обратную задачу, вот и всё. выше про это уже извинялся.
EugenO, не согласен, мы же смотрим не значения в точках, а скорость роста функции.
Или же, поясните подробнее, в чём именно на Ваш взгляд выражено это не удобство в сравнении.
Для меня удобство экспоненты в том, что она очень хороша для анализа. Она легко представима в виде a^x, элементарно дифференцируема (скорость роста) и интегрируема, причем многократно, связана со вторым замечательным пределом, кроме того, интуитивно (для меня) понятна, я ее график много раз рисовал в детстве и с удовольствием ассоциирую с всевозможными процессами, происходящими в реальной жизни, поэтому вижу естественным применение в асимптотике. В то же время не смогу указать ни одного естественного инерционного процесса, который изменялся бы «со скоростью выше экспоненциальной». Кстати, известна Stirling’s approximation для оценки факториала, а оценки экспоненты через факториал что-то не припомню (наверное, в ней смысла нет).
Хотелось бы узнать, зачем при анализе сложности алгоритмов Вы дифференцируете, интегрируете (причем многократно) экспоненту, как используете второй замечательный предел и формулу Стирлинга. Я не отрицаю, что, возможно, в теории сложности вычислений без этого нельзя обойтись. К сожалению, в данной области у меня очень скромный опыт((. А Вы, наверное, в этом вопросе отлично разбираетесь (может, даже на профессиональном уровне!). Поэтому очень интересно посмотреть, как применяет математический, комплексный и функциональный анализы в асимптотике настоящий специалист. Приведите, пожалуйста, пример.
Показательная функция, ее свойства и график (стр. 5 )
 | Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4 5 6 |
Сравнение роста показательной, логарифмической и степенной функций
1. Проверка д/з: вопросы? № 000 [1) 0; 2) 
; 3) 2; 4) 0,25]; 2) [D(f) = 
; f’(0) = 5
]; 3) [D(g) = (0,5; +¥); g’(1) = 0]; 4) [x ³ 0 и x ¹ 0,6].
2. Новый материал. Сравним поведение трех функций: показательной, логарифмической и степенной.
Определение. Функция y = f(x) растет быстрее функции y = g(x) при x ® +¥, если 
.
Примеры. 1) f(x) = xn + 1; g(x) = xn, где nÎN. 2) f(x) = e2x; g(x) = ex. Что это означает графически? [При x ® +¥ график f(x) располагается существенно выше графика g(x)]
Доказательство. Рассмотрим функцию h(x) = 
, x > 0, и найдем ее наибольшее значение. Так как h(x) непрерывна на (0; +¥) и «x > 0 h’(x) = 
, то h’(x) = 0 при x = a + 1, причем слева от этой точки функция возрастает, а справа – убывает (изобразить), поэтому, единственная критическая точка является точкой максимума. Следовательно, в этой точке функция принимает наибольшее значение. Пусть М = h(a + 1), тогда «x > 0 h(x) £ M, что равносильно доказываемому неравенству.
Домашнее задание: теория – по тетради; В.: № 000 (2; 3; Исследуйте функции: а) f(x) = 
; б) g(x) = ln3x – lnx и постройте их графики. 2) Решите неравенство: .
Исследование показательных, логарифмических и степенных функций и построение их графиков
1. Проверка д/з: вопросы? № 000 [2) 0; 3) 0; 7) 0]; 1) [См. рис. 1 а, б; а) нечетная; y = 0 – асимптота; f’(x) = 
; экстремумы: 
; f’’(x) = 2x(2×2 – 3)
; точки перегиба: x = 0; x = 
; б) D(g) = (0; +¥); g(x) = 0 при x = 1 или x = e или x = e–1; y = 0 – вертикальная асимптота; g’(x) = 
; точки экстремумов: x = 
; g’’(x) = 
; точки перегиба: x = 
]; 2) [x > 0].
2. Письменно (самостоятельно в тетрадях с проверкой на доске):
Исследуйте функции и постройте их графики:
[D(f) = (0; +¥) U N–. Если x = –n, где nÎN, то 
. Далее исследуем только на (0; +¥).
Непрерывна; «x > 0 f(x) > 0; 
; 
; асимптот – нет! f’(x) = xx(lnx + 1); x = e–1 – точка минимума; f(e–1) = 
; f’’(x) = xx – 1(1 + x(lnx + 1)2) > 0; f(1) = 1; f(2) = 4; f(3) = 27; f(–1) = –1; f(–2) = 0,25; f(–3) = 
. График – см. рис. 2а]
[D(g) = (–¥; 0) U (0; +¥); непрерывна; «xÎD(g) g(x) > 0; 
(y = 0 – горизонтальная асимптота при x ® –¥); 
(x = 0 – вертикальная асимптота); 
; 
; x = 1 – точка минимума; g(1) = e; 
> 0; g(2) = 0,25e3 » 5; g(–1) = e–3 » 0,05. График – см. рис. 2б]
В) h(x) = cosx – ln(cosx).
[D(h) = 
). «xÎD(h) h(x) > 0; 
(x = – вертикальная асимптота); h’(x) = tgx(1 – cosx) ³ 0 «xÎ[0; ). h’(x) = 0 при x = 0 – точка минимума; h(0) = 1; 
³ 0 «xÎ[0; ); h(
) = 0,5 + ln2 » 1,2. График – см. рис. 2в]
Домашнее задание: 1) Исследуйте функции: а) f(x) = 
; б) g(x) = 
; в) h(x) = esinx и постройте их графики. 2) Решите неравенство: .
Применение производных трех функций к оценке количества корней уравнений и доказательству числовых неравенств.
Преобразование иррациональных выражений.
1. Проверка д/з: вопросы? 1) [См. рис. 1 а – в (графики заготовить); а) f’(x) = 
; f’’(x) = 
; б) g’(x) = 
> 0; g’’(x) можно не находить! в) период – 2p; E(h) = [e–1; e]; h’(x) = esinx×cosx; h’’(x) = esinx×(1 – sinx – sin2x); точки перегиба: x » 
и x » 
]; 2) [(0,5; 1)]
Рассмотрим применение производных показательной, логарифмической и степенной функций и сравнение роста этих функций к задачам, связанным с количеством корней уравнений и сравнениям значений выражений.
2. Письменно (на доске и в тетрадях):
1) Найдите количество корней уравнений: а) 
; б) ex = lnx; в) x2 = 2x.
[а) три (изобразить): 0; ±1. Других корней нет, так как графики взаимно обратных возрастающих функций могут пересекаться только на прямой y = x. Докажите это утверждение [от противного; изобразить]. Кроме того, уравнение x3 = x не может иметь более трех корней. Существуют ли функции, графики которых пересекают прямую y = x бесконечное количество раз? [Да, например, y = x + sinx]; б) корней нет, так как «x > 0 ex > x > lnx (изобразить); так как функции f(x) = ex и g(x) = lnx взаимно обратные, то достаточно доказать первое неравенство. При x £ 0 оно очевидно; при x > 0 рассмотрим функцию h(x) = ex – x; h’(x) = ex – 1 > 0; в) три (изобразить): x1 0 и h’’(4) > 0, то есть, при x ³ 4 h’’(x) > 0, то есть, h’(x) возрастает и h’(4) > 0, поэтому h’(x) > 0, то есть, h(x) – возрастает и h(4) = 0, поэтому второй график выше первого и при x > 4 корней нет]
2) А) При каких основаниях логарифма существуют числа, равные своему логарифму?
[Найдем значения а | a > 0 и а ¹ 1, для которых уравнение x = 
имеет хотя бы один корень. А) При 0 1 рассмотрим функцию f(x) = x – на (0; +¥). На этом промежутке f(x) непрерывна и f’(x) = 1 – 
; f’(x) = 0 при x = 
> 0. Исследовав знаки производной, получим, что эта единственная критическая точка является точкой минимума, поэтому в ней f(x) принимает наименьшее значение. Для того, чтобы рассматриваемое уравнение имело корни необходимо и достаточно, чтобы 
£ 0. Учитывая, что а > 1, получим: 1 0; тогда lnf(x) = (x + 1)lnx; lng(x) = xln(x + 1); 
. Рассмотрим функцию h(t) = 
, которая определена и непрерывна на (0; +¥); h’(t) = 
e, то есть, h(t) убывает на (e; +¥). Следовательно, при x > e 
Û lnf(x) > lng(x) Þ f(x) > g(x) Þ 
> 
]
Повторим некоторые преобразования иррациональных выражений, которые мы изучали в ранее. Какие выражения (уравнения, неравенства) называются иррациональными? [Те, в которых переменные находятся под знаками радикалов]
3. Письменно (самостоятельно в тетрадях с проверкой на доске; записи!):
1) Вычислите: 
[]
2) Сравните: 
и 
[ > ; три способа! 1) Сравнить квадраты данных чисел; 2) сравнить числа 
и 
путем умножения и деления их на сопряженные; 3) используя производную, доказать, что функция f(x) = 
убывает на [0; +¥)]
Следующий урок – с/р!
Домашнее задание: 1) Сколько корней имеет уравнение: 
? 2) При каких значениях а уравнение xln|x| = a имеет единственный корень? 3) Исследуйте функцию f(x) = 
(без второй производной) и постройте ее график. 4) Сравните: а) 
и 
; б) 
и 
. 5) Постройте график функции: 
. 6) Докажите, что .
Самостоятельная работа №5. Решение простейших иррациональных уравнений
1. Проверка д/з: вопросы? 1) [Три корня (изобразить крупно): x1 = 2; x3 = 4; x1 0 f’(x) = lnx + 1; f(e–1) = e–1 – минимум]; 3) [См. рис. 2; f’(x) = 
; f(e) = 
– максимум];
4) [а) > , так как функция f(x) = xx убывает на [0; e–1]; б) 0. А) 
Û 
Û 
и таким образом сводится к предыдущему. Б) 
Û 
Û 
и тоже образом сводится к предыдущему.
Пример 2. 
Û 
Û 
Û 
Û 
Û 
Û x = 6.
3) Уравнения, решаемые заменой переменных.
Пример 3. 
. Пусть 
, тогда 3y = 
+ 2,5 Û 6y2 – 5y – 6 = 0 Û y = 
или y = 
. 1) > . 2) Рассмотрим функцию f(x) = 
, где x > 1; f’(x) = 
1, так как функция g(t) = tt возрастает при t > 1. Следовательно, f(x) – убывает, то есть > .
Последнее неравенство можно также доказать иначе: > > (для каждого перехода использовать сравнение среднего арифметического и среднего геометрического).
Решение иррациональных уравнений
2. Проверка д/з: вопросы? 1) [
]; 2) [5 – 
> 
];
