Общая форма: T(n) = aT(n/b) + f(n)
Поэтому я должен сравнить n ^ logb (a) с f (n)
если n^logba > f(n) - это случай 1 и T(n)=Θ(n^logb(a))
если n^logba ‹ f(n) случай 2 и T(n)=Θ((n^logb(a))(logb(a)))
Это правильно? Или я что-то неправильно понял?
А как же случай 3? Когда его применять?
Я думаю, вы неправильно поняли это. если n^logba > f(n) — случай 1 и T(n)=Θ(n^logb(a))
Здесь вам не следует беспокоиться о f (n), в результате вы получаете T (n) = Θ (n ^ logb (a)). f(n) является частью T(n)... и если вы получите результат T(n), то это значение будет включать f(n). так что нет необходимости рассматривать эту часть.
Дайте мне знать, если вам непонятно.
Повторения возникают в стратегии «разделяй и властвуй» при решении сложных проблем.
Что это решает?
T(n) = aT(n/b) + f(n).a должно быть больше или равно 1. Это означает, что проблема хотя бы один раз сводится к меньшей подзадаче. Нужна хотя бы одна рекурсия.b должно быть больше 1. Это означает, что при каждой рекурсии размер проблемы уменьшается до меньшего размера. Если b не больше 1, это означает, что наши подзадачи не меньшего размера.f(n) должно быть положительным для относительно больших значений n.Рассмотрим изображение ниже:
Допустим, у нас есть проблема размера n, которую нужно решить. На каждом шаге проблема может быть разделена на a подзадач, и каждая подзадача имеет меньший размер, причем размер уменьшается в b раз.
Приведенное выше утверждение простыми словами означает, что задачу размера n можно разделить на a подзадач относительно меньших размеров n/b.
Кроме того, приведенная выше диаграмма показывает, что в конце, когда мы разделили проблемы несколько раз, каждая подзадача будет настолько мала, что ее можно будет решить за постоянное время.
Для приведенного ниже вывода рассмотрим log по основанию b.
Предположим, что H — это высота дерева, тогда H = logn. Количество листьев = a^logn.
f(n)a * f(n/b)a * a * f(n/b2)number of leaves * θ(1). Это равно n^logaТеперь давайте предположим, что стоимость операции увеличивается значительным фактором на каждом уровне, и к тому времени, когда мы достигаем конечного уровня, значение f(n) становится полиномиально меньшим, чем значение n^loga. Тогда общее время выполнения будет сильно зависеть от стоимости последнего уровня. Отсюда T(n) = θ(n^loga).
Предположим, что стоимость операции на каждом уровне примерно одинакова. В этом случае f(n) примерно равно n^loga. Следовательно, общее время выполнения будет в f(n) раз больше общего количества уровней.
T(n) = θ(n^loga * logn), где k может быть >=0. Где logn будет высотой дерева для k >= 0.
Предположим, что стоимость операции на каждом уровне уменьшается в значимой степени на каждом уровне, и к моменту, когда мы достигаем конечного уровня, значение f(n) становится полиномиально больше, чем значение n^loga. Тогда общее время выполнения будет сильно зависеть от стоимости первого уровня. Отсюда T(n) = θ(f(n)).
Если вы заинтересованы в более подробном чтении и примерах для практики, посетите мою запись в блоге Master Method to Solve Повторы
