Найти $%\Theta$%-асимптотику рекуррентного соотношения $%F(n)=F(\frac{n}{6})+F(\frac{7n}{9})+2n$%.

Для $%n \leq 3$% $%F(n)=1$%.

Под основную теорему не подходит, хочется применить метод Акра-Баззи, однако получается уравнение $%\left(\frac{1}{6}\right)^p+\left(\frac{7}{9}\right)^p=1$% которое при целых $%p$% решения не имеет, и как хоть в чём-то его выразить не очень понятно.

Как быть в таких ситуациях?

задан 21 Май '17 17:35

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

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

Попробуем получить верхнюю оценку вида F(n)<=kn, где k -- константа. Рассуждая по индукции, имеем F(n/6)+F(7n/9)+2n<=(k(1/6+7/9)+2)n=(17k/18+2)n=kn при k=36. Для начальных значений n оценка F(n)<=36n справедлива. Тогда по индукции она будет верна и для всех значений.

С другой стороны, F(n)>=2n, откуда F(n)=Theta(n).

ссылка

отвечен 21 Май '17 23:25

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

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

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

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

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

отмечен:

×63
×48

задан
21 Май '17 17:35

показан
488 раз

обновлен
21 Май '17 23:25

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

по почте:

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

по RSS:

Ответы

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

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