Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
f1(n) = (ln n)^2;
f2(n) =(ln n)^ln n;
f3(n) = (3/2)^n ;
f4(n) = n2^n;
Расположите следующие 4 функции в порядке увеличения скорости роста (каждая функция есть O(следующая)), не исключено, что некоторые функции имеют одинаковую скорость
f1(n) = (ln n)^2;
f2(n) =(ln n)^ln n;
f3(n) = (3/2)^n ;
f4(n) = n2^n;
Оля, хотим обратиться к Вам лично. Вы проявили себя как ОЧЕНЬ хорошо подготовленный слушатель в области математической логики! Поэтому у нас к Вам небольшая просьба - не размещайте свой ответ первой:-) Давайте попробуем подождать, чтобы кто-нибудь другой дал ответ. Однако....Будем Вам признательны, если Вы поможете нам в обсуждении решений от других слушателей.
Хорошо))
f3. f1. f2. f4
А почему?
Извиняюсь за долгое молчание.
При решении я исходил из следующего: (ошибочно, сейчас обнаружил свои ошибки.)
Самая медленно растущая функция - это f3, т.к. скорость роста подобных функций являет самой маленькой, возведение константы в степень.
Вторая по скорости рост изначально f4 (тут допустил ошибку), это функция сходна с числами Ферма, не хватает только плюс единицы. Сейчас бы я её указал, как самую быстро растущую. Вторая по росту должна быть функция f1
Третьей по скорости я указал f2, эта логарифмическая функция превосходит по скорости рост функция f1.
Четвёртой, т.е. самой быстрой (ошибочно) я указал f1, как... откровенно говоря - не понимаю теперь сам.
Поэтому мой исправленный ответ следующий, f3, f1, f2, f4
f3 - это показательная функция. Почему Вы считаете, что она медленно растёт?
Да, опять ошибся, что-то в последнее время начал делать много ошибок. Вы правы. С это правкой получается, что f1, f2, f3, f4.