Подскажите, будьте добры, как приблизительно оценить скорость возрастания последовательности A068943 из OEIS?

Вот она: http://oeis.org/A068943

Как сравнить скорость её возрастания со скоростью возрастания функции, скажем, Аккермана?

Заранее благодарю!

задан 6 Авг '17 23:22

10|600 символов нужно символов осталось
1

Рост у этой последовательности не слишком большой. Как правило, при рассмотрении быстро растущих функций рассматривают отношение эквивалентности, при котором функции f(n) и f(Cn) считаются эквивалентными -- например, это касается $%2^n$% и $%3^n$%. В данном случае последовательность эквивалентна двойной экспоненте, то есть $%2^{2^n}$%. Действительно, формула для $%a_n$% имеет следующий вид: $$n(n-1)^{C_n^1}(n-2)^{C_{n+1}^2}\ldots2^{C_{2n-3}^{n-2}}1^{C_{2n-2}^{n-1}}.$$

Оценим сверху все основания степеней числом $%n$%, а биномиальные коэффициенты будем рассматривать из $%2n-2$% по $%0,1,\ldots,n-1$%. Их сумма меньше $%2^{2n-2}$%. Таким образом, $%n^{4^n}$% даёт верхнюю оценку. Нижняя оценка имеет такой же порядок.

Если сравнивать с функциями Аккермана, то данная последовательность растёт быстрее экспоненты, а следующая функция представляет собой "башню" экспонент вида $%2^{2^{\ldots^2}}$%, где двойка встречается $%n$% раз, то есть это намного больше.

ссылка

отвечен 7 Авг '17 9:20

@falcao, большое спасибо!

(8 Авг '17 16:10) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×128

задан
6 Авг '17 23:22

показан
349 раз

обновлен
8 Авг '17 16:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru