Оцените рекуррентное соотношение с помощью дерева рекурсий: $%T(n)=T(\frac{n}{9})+T(\frac{13n}{18}+10)+O(n)$%.

задан 21 Мар '16 2:21

Здесь самым обычным способом (по индукции) получается линейная верхняя оценка. При желании, это можно проиллюстрировать при помощи дерева, но вроде бы и так всё понятно. Ясно также, что лучше линейной оценка быть не может.

(21 Мар '16 2:26) falcao

@falcao, да, линейную оценку я даже могу доказать, но нужно именно дерево рекурсий. А т.к. второе слагаемое в правой части больше первого, то по его стремлению к 1 оценивается глубина дерева. Не пойму как тут оценивать, если присутствует 10.

(21 Мар '16 2:39) Uchenitsa

@Uchenitsa: если нужно решить непосредственно при помощи применения какого-то конкретного метода, то нужно иметь перед собой некий образец. Прибавление +10 тут никакой роли играть не должно, потому что можно чуть увеличить коэффициент при n (например, до 7/9), и тогда из соображений монотонности всё сводится к случаю без дополнительных слагаемых.

(21 Мар '16 2:42) falcao
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Вопрос отвечен и ответ принят". Закрывший - Uchenitsa 25 Мар '16 1:02

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

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

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

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

отмечен:

×159
×72
×65
×22

задан
21 Мар '16 2:21

показан
513 раз

обновлен
21 Мар '16 2:42

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

по почте:

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

по RSS:

Ответы

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

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