Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
1) f1(n) = n!;
2) f2(n) = n2;
3) f3(n) = ln n ;
4) f4(n) = n(ln n).
Вы здесь
Вопрос по Главе 7. Задача про скорость роста функций
28 марта, 2016 - 06:43
#1
Вопрос по Главе 7. Задача про скорость роста функций
1. f3(n)
2. f4(n)
3. f2(n)
4. f1(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!<n^n при n>1
Другое дело, что скорость роста n! не слишком хороша для сравнения, и не очень понятно, где ее можно использовать. Удобнее пользоваться показательной функцией (экспонентой).
Извините, для какого сравнения не слишком хороша скорость роста факториала?
Тут я ошибся, переклинило и я решал обратную задачу, вот и всё... выше про это уже извинялся.
EugenO, не согласен, мы же смотрим не значения в точках, а скорость роста функции...
Или же, поясните подробнее, в чём именно на Ваш взгляд выражено это не удобство в сравнении.
Для меня удобство экспоненты в том, что она очень хороша для анализа. Она легко представима в виде a^x, элементарно дифференцируема (скорость роста) и интегрируема, причем многократно, связана со вторым замечательным пределом, кроме того, интуитивно (для меня) понятна, я ее график много раз рисовал в детстве и с удовольствием ассоциирую с всевозможными процессами, происходящими в реальной жизни, поэтому вижу естественным применение в асимптотике. В то же время не смогу указать ни одного естественного инерционного процесса, который изменялся бы "со скоростью выше экспоненциальной". Кстати, известна Stirling’s approximation для оценки факториала, а оценки экспоненты через факториал что-то не припомню (наверное, в ней смысла нет).
Хотелось бы узнать, зачем при анализе сложности алгоритмов Вы дифференцируете, интегрируете (причем многократно) экспоненту, как используете второй замечательный предел и формулу Стирлинга. Я не отрицаю, что, возможно, в теории сложности вычислений без этого нельзя обойтись. К сожалению, в данной области у меня очень скромный опыт((. А Вы, наверное, в этом вопросе отлично разбираетесь (может, даже на профессиональном уровне!). Поэтому очень интересно посмотреть, как применяет математический, комплексный и функциональный анализы в асимптотике настоящий специалист. Приведите, пожалуйста, пример.
Супер!
Все верно!