Всем привет, эксперты! Необходимо решить рекуррентное отношение T(n)=2T(n/3)+n. Буду благодарен за помощь

задан 11 Ноя '17 2:25

изменен 11 Ноя '17 2:26

Под отношением в математике понимается нечто совсем другое. Здесь речь о рекуррентном соотношении.

Тут общая закономерность не совсем хорошая, но если нужна только асимптотика, то её получить несложно. Для степеней тройки получается точное значение T(3^m)=3^{m+1}-2^{m+1}, то есть функция растёт где-то линейно, или чуть медленнее. Типа, T(n)=3n-(3n)^log_3(2). Остальное зависит от того, с какой точностью это надо оценивать.

(11 Ноя '17 3:31) falcao

При n=2 имеем T(2)=2T(2/3)+2. И что здесь означает T(2/3) ?

(11 Ноя '17 3:55) abc

@abc: при асимптотических подсчётах берётся целая часть. То есть T(2/3)=T(0)=0.

(11 Ноя '17 4:04) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×246
×154
×65
×22

задан
11 Ноя '17 2:25

показан
343 раза

обновлен
11 Ноя '17 4:04

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

по почте:

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

по RSS:

Ответы

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

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