Решение уравнения с использованием обобщения основной теоремы

Прошу помощи в объяснении того, как работает доказательство. Я видел примеры этого, но не могу понять.

Докажите следующее

Решение уравнения

T(n) = aT(n/b) + Θ(n^k log^p n), где a ≥ 1, b > 1, p ≥ 0

T(n) = O(n^{log_b a}), если a > b^k
T(n) = O(n^k log^p+1 n), если a = b^k
T(n) = O(n^k log^p (n)) если a ‹ b^k

Вот скриншот вопроса в лучшем формате

Это обобщение основной теоремы.

Nyan Wolf 29.11.2016 источник

comment

Вы спрашиваете; предоставить доказательство основной теоремы?? Это хорошо и действительно решенная проблема - стр. 76 en.wikipedia.org/wiki/Introduction_to_Algorithms - thespinkus 29.11.2016

comment

Вопрос требует доказать данную теорему. Я не знаком с такой теоремой и был бы признателен за объяснение того, как подойти к доказательству и почему такое доказательство приемлемо. Я уже просмотрел другие ответы, но мне трудно понять концепции, лежащие в основе доказательства. - Nyan Wolf 29.11.2016

comment

Совет: возьмите «Введение в алгоритмы» из библиотеки и перейдите на стр. 76. Это очень хороший текст. Очень доказательство. - thespinkus 29.11.2016

comment

Я читал его, но мне трудно его понять. - Nyan Wolf 29.11.2016

comment

Да, книга немного запутана. - fractal 29.11.2016

comment

Может быть, если вы хотите объяснения, опишите, какие существующие опубликованные доказательства вас беспокоят. - thespinkus 29.11.2016

comment

В книге показано обобщенное объяснение O (n). Теперь я ищу, как применить подобное доказательство к O (n ^ k log ^ p n). - Nyan Wolf 29.11.2016

Ответы (1)

arrow_upward
0
arrow_downward

Для некоторого x =log(n)/log(b) имеем n=b^x. Разделите уравнение на a^x

T(b^x)/a^x = T(b^x-1)/a^x-1 + Θ((b^k/a)^x·x^p·log^p b)

Сумма членов m^p·q^m для m ‹ x равна

ограничен константой при q ‹ 1
растет как x^p+1 для q = 1
доминирует последний член x^p·q^x для q > 1

Признание q=b^k/a и подстановка обратно дает результат

для a ‹ b^k: T(b^x)=O(a^x) или T(n)=O(n^лог_ба)
для a = b^k: T(b^x)=O(x^p+1·a^x) , или T(n)=O(n^log_ba·log^p+1n )
для a > b^k: T(b^x)=O(x^p·b^kx), или T(n)=O(n^k·log^pn)

Lutz Lehmann 29.11.2016

Решение уравнения с использованием обобщения основной теоремы

Ответы (1)

Похожие вопросы