Повторение T (n) = 2T (n / 2) + (n-1)

Question

У меня есть это повторение:

T(n)= 2T(n/2) + (n-1)

Моя попытка заключается в следующем:

дерево выглядит так:дерево: (n / (2 ^h )) - 1 = 1 ⇒ h = lg n - 1 = lg n - lg 2

стоимость последнего уровня: 2 ^h = 2 ^{lg n - lg 2} = (1/2) n стоимость всех уровней до уровня h-1: Σ _{i = 0,..., lg (2n)} n - (2 ⁱ -1), который является геометрическим рядом и равен (1/2) ((1/2) n-1)

Итак, T (n) = Θ (n lg n)

мой вопрос: так ли это?

Answer 1

Нет, это не так. Вы неверно оценили стоимость последнего уровня, поэтому то, что вы извлекли из этого, также неверно.

(Полагаю, вы хотите сами найти сложность, поэтому больше никаких подсказок, если вы не спросите.)

Редактировать: некоторые подсказки по запросу

Чтобы найти сложность, обычно полезно использовать метод рекурсивного применения уравнения и вставить результат в первое,

T(n) = 2*T(n/2) + (n-1)
     = 2*(2*T(n/4) + (n/2-1)) + (n-1)
     = 4*T(n/4) + (n-2) + (n-1)
     = 4*T(n/4) + 2*n - 3
     = 4*(2*T(n/8) + (n/4-1)) + 2*n - 3
     = ...

Это часто приводит к закрытой формуле, которую вы можете доказать с помощью индукции (вам не нужно проводить доказательство, если у вас достаточно опыта, тогда вы видите правильность, не записывая доказательство).

Спойлер: Вы можете посмотреть сложность практически любого ресурса, имеющего дело с Основной теоремой .

Answer 2

Это можно легко решить с помощью Теорема Мастера .

У вас есть a=2, b=2, f(n) = n - 1 = O(n) и, следовательно, c = log2(2) = 1.Это попадает в первый случай теоремы магистра, что означает, что сложность составляет O(n^c) = O(n)