Как получить O (n) из T (n) = T (n / 2) + n?

Question

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

T(n) = T(n/2) + n
T(n) = T(n/4) + 2n
T(n) = T(n/8) + 3n
.
.
.
T(n) = T(n/2^k) + kn
k=logn -> T(1) + **nlogn**

в чем проблема?

Answer 1

В последних главах Основы алгоритмов - Ричард Э. Неаполитан.pdf вы найдете несколько способов решения рекуррентных отношений. как-то так: 1- дерево повторений 2- изменить переменные и дифференциальные уравнения

, а также вы можете увидеть ссылку

Answer 2

Для решения рекуррентного отношения с нуля необходимо выполнить два шага:

1. Каким-то образом найти ответ
2. Доказать, что он правильный

" Каким-то образом найти ответную часть «может быть сложно». Обычные способы состоят в том, чтобы расширить несколько терминов и экстраполировать, как это сделал Родойф в другом ответе, составить график / составить таблицу и взглянуть на нее или распознать знакомый шаблон. Все эти способы работают очень хорошо для вашего примера.

Давайте поместим несколько точек в таблицу или график (пусть C = T (1)):

 n  |  T(n)
===========
 1  |   C
 2  |   C + 2
 4  |   C + 6
 8  |   C + 14
16  |   C + 30

мне нравится T (n) = 2n - 2 + C

Мы можем доказать T (2 ^x ) = 2 ^{x + 1} - 2 + C быть правильным для всех x> = 0 по индукции:

• Если x = 0 , то 2 ^{x + 1} - 2 + C = C, т. T (2 ^x ) = 2 ^{x + 1} - 2 + C, из таблицы
• Для любого x, T ( 2 ^x ) = 2 ^{x + 1} - 2 + C ⇒ T (2 ^{x + 1} ) = 2 ^{x + 1} - 2 + C + 2 ^{x + 1} = 2 ^{(x + 1) + 1} - 2 + C, путем подстановки

Таким образом, тот факт, что формула верна для n = 2 ⁰ , подразумевает, что она верна для всех n = 2 ^x

Для охвата всех других значений n, вы также должны заметить, что всегда есть 2 ^x между n и 2n и между n / 2 и n, и что их значения T (2 ^x ) связаны с T (п).

Это достаточно трудоемко для одного отдельного случая ... вот почему мы помним основную теорему, которая была доказана для всех случаев, которые соответствуют ее образцам.

Answer 3

T(n)=T(n/2)+n=T(n/2^2)+n/2+n=T(n/2^3)+n/2^2+n/2+n= ... =  
=T(n/2^k)+n/2^(k-1)+n/2^(n-2)+...+n=  
=T(n/2^k)+n*(1-(1/2)^k)/(1-1/2)=  
=T(n/2^k)+2*n*(1-(1/2)^k)<=  
<=T(n/2^k)+2*n  

Если вы знаете, что T - это функция, определенная и ограниченная в (0,0 + e) ​​для некоторого небольшого e> 0, то вы можете заключить, что T есть O (n).