Какие функции растут быстрее таблица
Подводя итоги, при анализе алгоритмов нас будет интересовать скорее класс скорости роста, к которому относится алгоритм, нежели точное количество выполняемых им операций каждого типа. Относительный «размер» функции будет интересовать нас лишь при больших значениях переменной х.
Некоторые часто встречающиеся классы функций приведены в нижеследующей таблице. В этой таблице собраны значения функций из данного класса на широком диапазоне значений аргумента.
 |
| Классы роста функций |
 |
| Графики функций: log2n , n , nlog2n , n 2 , n 3 , и 2 n |
Видно, что при небольших размерах входных данных значения функций отличаются незначительно, однако при росте этих размеров разница существенно возрастает. Поэтому мы и будем изучать, что происходит при больших объемах входных данных, поскольку на малых объемах принципиальная разница оказывается скрытой.
Быстрорастущие функции доминируют над функциями с более медленным ростом. Поэтому если мы обнаружим, что сложность алгоритма представляет собой сумму двух или нескольких таких функций, то будем часто отбрасывать все функции кроме тех, которые растут быстрее всего.
Если, например, мы установим при анализе алгоритма, что он делает x 3 — 30x сравнений, то мы будем говорить, что сложность алгоритма растет как x 3 . Причина этого в том, что уже при x = 100 входных данных разница между x 3 и x 3 — 30x составляет лишь 0,3%.
Использование пределов для сравнения порядка роста двух функций
Несмотря на то что без строгих определений множеств О, Q, W нельзя обойтись при доказательстве их абстрактных свойств, они редко используются при сравнении порядков роста двух конкретных функций. Дело в том, что существует более удобный метод выполнения этой оценки, основанный на вычислении предела отношения двух рассматриваемых функций. Может существовать три основных
Для двух первых случаев 
для двух последних 
а для второго 
. Методы основанные на вычислении пределов более удобны, чем рассмотренные выше, основанные на определении множеств. При рассмотрении след. примеров будем пользоваться правилом Лопиталя 
и формулой Стирлинга 
Пример 1. Сравните порядки роста функций n(n — 1)/2 и n 2 .
Поскольку предел равен положительной константе, обе функции имеют одинаковый порядок роста, что записывается как 
Пример 2. Сравните порядки роста функций log2n и .
Поскольку предел равен нулю, функция log2n имеет меньший порядок роста, чем . (Так как 
, то для этого случая можно использовать так называемую форму записи "с маленькой о": 
. В отличие от прописной греческой "О" при анализе алгоритмов строчная "о" используется довольно редко.)
Пример 3. Сравните порядки роста функций n! и 2 n . Воспользовавшись формулой Стирлинга, получим:
Следовательно, хотя функция 2 n растет очень быстро, функция n! растет еще быстрее, что записывается так: 
Основные классы эффективности.
Хотя в основах анализа алгоритмов к одному классу относят все функции, чей порядок роста одинаков с точностью до постоянного множителя, существует бесконечное множество подобных классов. Например, порядок роста показательной функции а n зависит от значения основания а. Поэтому временную эффективность большого количества алгоритмов можно отнести всего к нескольким классам. Эти классы, их названия, а также некоторые пояснения, приведены в таблице в соответствии с возрастанием их порядка роста.
функции — Какая функция растет быстрее?
Скажите, пожалуйста, как определить какая из этих функций растет быстрее?
задан 11 Дек ’19 22:02
1 ответ
Мы знаем, что $%H_n$% растет примерно как $%\ln n$%. Факториал такого числа, согласно формуле Стирлинга, имеет рост порядка $%(\frac<\ln n>e)^<\ln n>$%. Число Фибоначчи с номером $%m$% растёт примерно как $%\phi^m$%, где $%\phi=\frac<1+\sqrt5>2$%. Логарифм первой из функций имеет порядок роста $%C(\frac<\ln n>e)^<\ln n>$%. Для второй функции это $%\sqrt
Как расположить функции в порядке увеличения скорости роста?
Мой вариант:
11 14 5 6 12 15 7 1 8 9 13 2 17 3 4 16 10
Он неправильный.
- Вопрос задан более трёх лет назад
- 12329 просмотров
- Вконтакте
Попробуйте вот такой вариант : 14 11 5 12 6 15 1 8 9 13 2 7 17 3 4 16 10
У меня есть некоторые основания на него полагаться.