Верно ли, что если $%f(n), g(n)$% - неограниченные положительные неубывающие функции, такие что $%\ln f(n) \sim \ln g(n)$% при $%n \rightarrow \infty$%, то $%\frac{f(n)}{g(n)} = O(g(n))$%? Верно ли, что $%\frac{f(n)}{g(n)} = o(g(n))$%?

задан 10 Окт '19 18:57

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

Первое условие верно всегда. Второе -- при дополнительном предположении, что функции стремятся к бесконечности (в противном случае их можно взять одинаковыми константами).

Положим $%f(n)=e^{\phi(n)}$%, $%g(n)=e^{\psi(n)}$%. Тогда отношение $%\frac{\phi(n)}{\psi(n)}$% стремится к 1, и можно положить $%\phi(n)=\psi(n)(1+\alpha_n)$%, где $%\alpha_n\to0$%.

Далее имеем $%\frac{f(n)}{g(n)}=e^{\phi(n)-\psi(n)}=e^{\psi(n)\alpha_n}=g(n)^{\alpha_n}$%. Такое отношение само по себе может стремиться куда угодно, однако оно всегда есть $%O(g(n))$%. Если же известно, что $%g(n)\to\infty$%, то $%\frac{g(n)^{\alpha_n}}{g(n)}=\frac1{g(n)^{1-\alpha_n}}\to0$%, то есть $%\frac{f(n)}{g(n)}=o(g(n))$% на бесконечности.

ссылка

отвечен 10 Окт '19 19:47

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×27
×15

задан
10 Окт '19 18:57

показан
265 раз

обновлен
10 Окт '19 19:47

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

по почте:

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

по RSS:

Ответы

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

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