Повторяемость T(n)= 2T(n/2) + (n-1)

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

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

Моя попытка выглядит следующим образом:

дерево такое:

T(n) = 2T(n/2) + (n-1)
T(n/2) = 2T(n/4) + ((n/2)-1)
T(n/4) = 2T(n/8) + ((n/4)-1) 
...
  • высота дерева: (n/(2h))-1 = 1 ⇒ h = lg n - 1 = lg n - lg 2
  • стоимость последнего уровня: 2h = 2lg n - lg 2 = (1/2) n
  • стоимость всех уровней до уровня h-1 : Σi=0,...,lg(2n) n - (2i-1), что является геометрический ряд и равен (1/2)((1/2)n-1)

So, T(n) = Θ(n lg n)

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


recurrence big-o asymptotic-complexity
person Sosy    schedule 29.11.2011    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

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
     = ...

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

Спойлер: вы можете посмотреть сложность почти в любом ресурсе, посвященном Главной теореме.

person Daniel Fischer    schedule 29.11.2011
comment
стоимость последнего уровня = # узлов * T(1) = 2^h, где h= lg2n.. Я не знаю, где не так :S - person Sosy; 30.11.2011
comment
хм извините, а что 2^(lg n)? :$ - person Sosy; 30.11.2011
comment
@Sosy Вы написали lg2n для логарифма, я предпочитаю отделять функцию от аргумента пробелом. Поскольку здесь мы имеем дело исключительно с логарифмами по основанию 2, я опустил основание. - person Daniel Fischer; 30.11.2011
comment
давайте продолжим это обсуждение в чате - person Sosy; 30.11.2011

arrow_upward
0
arrow_downward

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

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

person Salvador Dali    schedule 14.12.2015