Условие:
Дано неравенство:\nT((r+1)n) \le (2r+1)T(n) + Cn
где C > 0 , r \ge 0 , n — размер задачи.
Нужно доказать, что для n = (r+1)^k выполняется:\nT((r+1)^k) \le C(2r+1)^k
(предполагая, что T(1) = C или что база T(1) подходит под это).
Решение:
При условии T((r+1)n) ≤ (2r+1)T(n) + C·n для всех n, при выборе n = (r+1)^k (k ≥ 0) и при подходящей базе (например, если T(1)=C) верно неравенство
T((r+1)^k) ≤ C·(2r+1)^k.
Обратите внимание, что при такой постановке условия надо выбирать константу C (или базовое значение T(1)) таким образом, чтобы индуктивное доказательство работало. Далее приведём пошагово рассуждение.
——————————————
Шаг 1. База индукции
Выберем k = 0, тогда n = (r+1)^0 = 1. По условию базы предполагаем, что T(1) удовлетворяет неравенству, то есть T(1) ≤ C. С д...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи