Проблемы рекуррентных отношений

Question

У меня были следующие рекуррентные отношения на тесте, и я их неправильно понял, я не уверен, почему.

 1. T(n) = 2T(n/4) + O(n^0.5)

Использование MT: a = 2, b = 4, f (n) = n ^ 0,5

Сравнение n ^ (log_4 (2)) с n ^ 0.5 => n ^ 0.5 == n ^ 0.5

Таким образом, случай 3: & Theta; (n log n)

Видимо, это неправильно, не знаю почему.

 2. T(n) = 3T(n/4) + O(n^0.75)

Использование MT: a = 3, b = 4, f (n) = n ^ 0,75

Сравнение n ^ (log_4 (3)) с n ^ 0,75

Таким образом, случай 1: & Theta; (n ^ log_4 (3))

 3. T(n) = T(n/2) + T(n/3) + O(n log n)

Это не в форме, которую можно решить с помощью MT, и я не могу легко найти p-значение без помощи. Таким образом, я получил удар в темноте и ошибся. Понятия не имею, с чего начать.

 4. T(n) = 2T(n/2) + n log n

Использование MT: a = 2, b = 2, f (n) = n log n

Сравнение n ^ log_2 (2) с n log n => n ^ 1 с n log n

Случай 2: & Theta; (n log n)

Answer 1

Возможно, вы неправильно прочитали или пропустили некоторые детали основной теоремы. Будет ссылаться на статью в Википедии .

---

1)

Во втором случае говорится, что:

Поскольку c_crit = 0.5 и k = 0, конечная сложность равна:

Вы только что пропустили показатель степени на n впереди.

---

2)

Это правильно.

---

4)

Вы пропустили еще одну деталь здесь: k = 1, и необходимо добавить дополнительный коэффициент log n:

---

3)

Это немного сложнее. Использование метода Акра-Бацци :

Чтобы вычислить для показателя p, просто используйте Ньютон-Рафсон на своем калькуляторе - дает p = 0.787885.... Выполнение интеграции по частям:

Подставляя в: