Главный метод - почему он не может решить T (n) = 4 * T (n/2) + (n^2)/logn?Главный метод - почему он не может решить T (n) = T (n/2) + n^2/logn?
Я понимаю, что может решить рецидивы типа Т (п) = аТ (п/б) + F (п)
В MIT OCW они упоминали, что он не может решить вышеупомянутую рецидив, хотя. Может ли кто-нибудь объяснить вам причину?
Ответ на Т (п/2) + (п^2)/LOGN:
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does not apply,
f(n) = Ω(n^e) for e = 1, BUT
a*f(n/b) <= c*f(n) for no c<1 (works out that c >= 2)
Таким образом, мы не можем применить любой случай. Помимо этого, я не очень хороший - и снова я не на 100% на этот ответ.
Следующая была до этого редактирования, и предполагается, что вопрос в отношении Т (п) = Т (п/2) + п^(2logn) Я абсолютно уверен, что это дело 3 теоремы.
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does apply,
a*f(n/b) <= c*f(n) for some c<1 (works out that c >= 0.5)
and f(n) = Ω(n^e) for e = 1
Возможно, я ошибаюсь, поэтому проверьте и дайте мне знать!
Я немного изменил вопрос (поставьте несколько скобок, чтобы было ясно, что разделено на что и что поднято до чего), поэтому надеюсь, теперь это яснее. –
f (n) = (n^2)/logn и n^(log a/log b). Вычислите разницу между двумя вышеуказанными функциями.
отношение = (п^2/п лог)/(п^2)
Отношение оказывается логарифмическая. Это рекуррентное отношение попадает в промежуток между случаем 2 и случаем 3. Таким образом, теорема Мастера для этого рекуррентного отношения неприменима.
Теорема Мастера применима, когда разница между двумя указанными выше функциями является полиномиальной.
его, потому что во всех указанных трех случаях вы не можете оправдать положительную асимптотику. что означает, что при n-> бесконечности n^2/lg (n) -> бесконечность, это просто означает n^e = w (lg (n)), которое можно перефразировать как «функция не может содержаться» без верхней границы существует для процедур деления и завоевания.
Похоже, что третий случай, когда f (n) больше, но он также должен удовлетворять условию регулярности (af (n/b) < = cf (n) для некоторого c in (0,1)). Здесь функция не удовлетворяет условию регулярности, поэтому мастер-метод не работает здесь
Не могли бы вы предоставить ссылку на то, где они говорят, что это невозможно решить? Кроме того, это (n^2) logn или n^(2logn) – blitzen
Не совсем вопрос программирования. Основная теорема дает * некоторые * рекуррентности типа T (n) = aT (n/b) + f (n), но не все. Существуют ограничения на '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' '' ' ваш вопрос спорный!). См. Http://en.wikipedia.org/wiki/Master_Theorem для более подробной информации, или я думаю, вы можете найти ту же информацию и многое другое, где-то в материале Массачусетского технологического института. –
... и если ваш вопрос «почему существуют ограничения на' a', 'b' и' f'?, То я полагаю, что вам действительно нужно проконсультироваться с доказательством теоремы Учителя, чтобы понять, где нужны ограничения чтобы получить результаты. –