Задача: Пусть для положительной функции $%f(n)$% выполнено $%f(n)=(3+o(1))^n+\Theta(n^{100})$%. Верно ли в общем случае, что $%\log{f(n)}=\Theta(n)$%?

Мой ход мыслей: Переписываем исходное равенство как $%f(n)=(3+u(n))^n+v(n)$%, где $%u(n)=o(1)$% и $%v(n)=\Theta(n^{100})$%. Тогда $%\log{f(n)}=n\log{(3+u(n))}+\log{v(n)}$%.

  1. $%v(n)=\Theta(n^{100}) \Rightarrow \exists C_1 > 0, C_2 > 0, n_0: \forall n \geq n_0 \rightarrow C_1 n^{100} \leq v(n) \leq C_2 n^{100}$%. Тогда $%\log{C_1}+100\log{n}\leq \log{v(n)}\leq \log{C_2}+100\log{n}$%. Здесь не очень понятно, верно ли, что отсюда $%\log{v(n)}=\Theta(\log{n})$% или $%\log{v(n)}=\Theta(n)$%? Как в таких случаях подбирать константы?
  2. Далее, $%u(n)=o(1)\Rightarrow\forall C > 0 \exists n_0: \forall n\geq n_0 \rightarrow u(n)< C$%. Отсюда $%3+u(n)=o(1)$% и $%\log(3+u(n))=o(1)\Rightarrow n\log(3+u(n))=o(n)$%.

Получается в итоге, что $%\log{f(n)}=o(n)+\Theta(n)$% или (в зависимости от ответа на вопрос из пункта 1) $%\log{f(n)}=o(n)+\Theta(\log{n})$%. Возникает ещё один вопрос, может ли сумма, содержащая $%o(n)$% быть $%\Theta(n)$%? (по логике вроде бы не должно такого быть, но как обосновать не понимаю). Ну и собственно вопрос как мои рассуждения можно развить в решение, или просто как решить задачу в целом?

задан 20 Май '17 21:49

изменен 20 Май '17 21:54

@Alevtina: у Вас во втором абзаце написано, что логарифм суммы равен сумме логарифмов. Это неправильно.

Здесь достаточно заметить, что n^{100}=o(3^n), так как экспонента растёт быстрее степени. То есть вторым слагаемым можно пренебречь. Тогда ln f(n) = n ln(3+o(1))=n ln 3 +o(n), и логарифм подобен линейной функции.

(20 Май '17 22:20) falcao

@falcao Точно, очень глупая ошибка Извиняюсь, не очень поняла два момента: 1) Не получается ли здесь тоже логарифм суммы равным сумме логарифмов n ln(3+o(1))=n ln 3 +o(n) 2) Ну и собственно вопрос из поста: может ли сумма, содержащая o(n) быть Θ(n)? Ведь o(n) можно провести аналогию со строгим неравенством, а Θ(n) требует нестрогое неравенство с двух сторон. Или при расчёте Θ(n) нас интересует только самое быстрорастущее слагаемое и nlog(3) растёт быстрее o(n) и мы на него просто забиваем?

(20 Май '17 22:38) Alevtina

@Alevtina: для любой непрерывной функции h верно h(x+o(1))=h(x)+o(1). Для случая ln было использовано именно это свойство.

Если какая-то функция имеет вид "почти линейной", то есть Сn+o(n), то именно это и есть, насколько я понимаю, Theta(n). Строгое или нестрогое неравенство -- это совершенно не важно, а для Cn+o(n) мы имеем (C+eps)n сверху и (C-eps)n снизу для любого достаточно маленького положительного eps.

(20 Май '17 23:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×243
×48
×7

задан
20 Май '17 21:49

показан
376 раз

обновлен
20 Май '17 23:10

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

по почте:

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

по RSS:

Ответы

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

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