Перейти к содержимому

Какие функции растут быстрее таблица

  • автор:

Какие функции растут быстрее таблица

Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций каждого типа. Относительный «размер» функции будет интересовать нас лишь при больших значениях переменной х.

Некоторые часто встречающиеся классы функций приведены в нижеследующей таблице. В этой таблице собраны значения функций из данного класса на широком диапазоне значений аргумента.

Классы роста функций

Графики функций: log2n , n , nlog2n , n 2 , n 3 , и 2 n

Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Поэтому мы и будем изучать, что происходит при больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.

Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего.

Если, например, мы установим при анализе алгоритма, что он делает x 3 — 30x сравнений, то мы будем говорить, что сложность алгоритма растет как x 3 . Причина этого в том, что уже при x = 100 входных данных разница между x 3 и x 3 — 30x составляет лишь 0,3%.

Сравнение функций по скорости роста

следовательно, функция y = x k , k > 0, растет быстрее при x → +∞ , чем y = log a x, a > 1.

Лекция №1 Основные теоремы дифференциального исчисления проф. Дымков М.П. 7

Для любого k > 1, в том ч исле и сколь угодно большого, справедливо неравенство n — 1 < k ≤ n , где n – натуральное число. Применив правило Лопиталя n раз, получим

k ( k − 1). ( k − n + 1)

a x ln n a x n − k

где величина n − k > 0 . Числитель дроби – постоянное число, знаменатель неограниченно возрастает, предел этой дроби равен нулю. Итак, функция

растет быстрее при x → +∞ , чем y = x k ,

неравенство n < a ≤ n + 1. Запишем дробь следующим образом

где произведение последних

дробей заменено на

наибольшую из них в степени x − n .

С другой стороны, отношение a x не может быть отрицательным. Итак, предел x !

рассматриваемого отношения функций ограничен сверху нулем и не может

быть меньше нуля. Поэтому lim

= 0 . Величина всех остальных пределов

заключена между нулем и единицей. Следовательно, произведение этих

пределов есть нуль. Итак, x lim →+∞ x x x ! = 0 . Функция y = x x самая быстрорастущая из перечисленных функций при x → +∞ .

Формулы Маклорена и Тейлора

Эти формулы являются одними из основных формул математического анализа и имеют многочисленные приложения.

Рассмотрим многочлен n -й степени

P ( x ) = a 0 + a 1 x + a 2 x 2 + . + a n x n .

Лекция №1 Основные теоремы дифференциального исчисления проф. Дымков М.П. 8

Его можно представить в виде суммы степеней переменной х, взятых с некоторыми коэффициентами. Продифференцируем его n раз по х, найдем значения многочлена и его производных в точке x = 0, выразим из каждого полученного выражения коэффициенты a 0 , a 1 . a n , разместив результаты в трех

Как расположить функции в порядке увеличения скорости роста?

Мой вариант:
11 14 5 6 12 15 7 1 8 9 13 2 17 3 4 16 10
Он неправильный.

  • Вопрос задан более трёх лет назад
  • 12338 просмотров
  • Facebook
  • Вконтакте
  • Twitter

OLS

Попробуйте вот такой вариант : 14 11 5 12 6 15 1 8 9 13 2 7 17 3 4 16 10
У меня есть некоторые основания на него полагаться.

Какая функция растет быстрее

Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций каждого типа. Относительный «размер» функции будет интересовать нас лишь при больших значениях переменной х.

Некоторые часто встречающиеся классы функций приведены в нижеследующей таблице. В этой таблице собраны значения функций из данного класса на широком диапазоне значений аргумента.

Классы роста функций
Графики функций: log2n , n , nlog2n , n 2 , n 3 , и 2 n

Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Поэтому мы и будем изучать, что происходит при больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.

Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего.

Если, например, мы установим при анализе алгоритма, что он делает x 3 — 30x сравнений, то мы будем говорить, что сложность алгоритма растет как x 3 . Причина этого в том, что уже при x = 100 входных данных разница между x 3 и x 3 — 30x составляет лишь 0,3%.

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

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

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

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

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

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!).

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

Ольга, но ведь 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. Только я не поняла, к чему данное замечание относилось. Поясните, пожалуйста.

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

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

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

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

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

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

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

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

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

Например, n!<n^n при n>1

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

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

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

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

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

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

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

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

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

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

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