Смущен на повторение и Big O

Question

Я знаю, что T (n) = T (n / 2) + θ (1) может быть результатом до O (Log N) и моя книга сказала, что это случай бинарного поиска. Но откуда ты это знаешь? Это просто тот факт, что бинарный поиск каждый раз режет проблему пополам, так что это O (Log N)?

And T(n) = 2T(n/2) + θ(1) 

Почему результат равен O (N), а не O (Log N), когда алгоритм также делится пополам каждый раз.

Then T(n) = 2T(n/2) + θ(n)

может быть результатом O (N Log N)? Я вижу, что O (N) от θ (n) и O (Log N) от T (n / 2)

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

Заранее спасибо!

Answer 1

Интуитивное решение этих проблем - увидеть результат при развертывании рекурсивной формулы:

Предположим, что Theta (1) на самом деле равно 1, а Theta (n) равно n, для простоты

T(n) = T(n/2) + 1 = T(n/4) + 1 + 1 = T(n/8) + 1 + 1 + 1 = ... = 
= T(0) + 1 + ... + 1 [logN times] = logn

T'(n) = 2T'(n/2) + 1 = 2(2T'(n/4) + 1) + 1 = 4T'(n/4) + 2 + 1 = 
= 8T'(n/4) + 4 + 2 + 1 = ... = 2^(logn) + 2^(logn-1) + ... + 1 = n + n/2 + ... + 1 = 
= 2n-1

T''(n) = 2T(n/2) + n = 2(2T''(n/2) + n/2) + n = 4T''(n/4) + 2* (n/2) + n = 
= 8T''(n/8) + 4*n/4 + 2*n/2 + n = .... = n + n + .. + n [logn times] = nlogn

Чтобы формально доказать эти уравнения, вы должны использовать индукция . Предположим, T(n/2) = X, а с его помощью - доказать T(n) = Y, как и ожидалось.

Например, , для первой формулы [T(n) = T(n/2) + 1] - и предположим, что основание равно T(1) = 0
База тривиально справедлива при n = 1
Предположим T(n) <= logn для любого k <= n-1 и докажите это для k = n
T(n) = T(n/2) + 1 <= (induction hypothesis) log(n/2) + 1 = log(n/2) + log(2) = log(n/2*2) = log(n)

Answer 2

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

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

, где n = 64.Давайте сложим, сколько алгоритм занимает на каждом шаге:

T(64) = T(32) + 1 ... 1 so far
T(32) = T(16) + 1 ... 2 so far
T(16) = T(08) + 1 ... 3 so far
T(08) = T(04) + 1 ... 4 so far
T(04) = T(02) + 1 ... 5 so far
T(02) = T(01) + 1 ... 6 so far
T(01) = 1         ... 7 total

Итак, мы можем видеть, что алгоритм занимает «1» время на каждом шаге.И, так как каждый шаг делит входные данные пополам, общая работа - это количество раз, которое алгоритм должен был разделить входными данными на два ... что составляет log2 n.

Далее, давайте рассмотрим случай, когда

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

Однако, чтобы упростить ситуацию, мы будем строить из базового случая T (1) = 1.

T(01) = 1           ... 1 so far 

, теперь мы должны сделать T (01) дваждыи затем добавьте один, так что

T(02) = 2T(01) + 1  ... (1*2)+1 = 3

теперь мы должны сделать T (02) дважды, а затем добавить один, так что

T(04) = 2T(02) + 1 ... (3*2)+1  = 7
T(08) = 2T(04) + 1 ... (7*2)+1  = 15
T(16) = 2T(08) + 1 ... (15*2)+1 = 31
T(32) = 2T(16) + 1 ... (32*2)+1 = 63
T(64) = 2T(32) + 1 ... (65*2)+1 = 127

Итак, мы можем видеть, что здесь алгоритм имеетвыполнено 127 работ - что равно входу, умноженному на константу (2) и плюс константу (-1), которая равна O (n).По сути, эта рекурсия соответствует бесконечной последовательности (1 + 1/2 + 1/4 + 1/8 + 1/16), сумма которой равна 2.

Попробуйте использовать этот метод для T (n) = 2T (n / 2) + n и посмотрите, имеет ли это для вас смысл.

Answer 3

Одним из визуальных решений для нахождения T (n) для рекурсивного уравнения является набросок дерева, тогда: T(n) = number of nodes * time specified on each node.

В вашем случае T(n) = 2T(n/2) + 1
Я пишу the one в самом узле и расширяю его до двух узлов T(n/2)
Обратите внимание T(n/2) = 2T(n/4) + 1, и снова я делаю то же самое для него.

            T(n) + 1
           /         \     
       T(n/2)+1      T(n/2)+1
      /     \           /     \
 T(n/4)+1  T(n/4)+1   T(n/4)+1  T(n/4)+1
 ...   ...  ..  ..      ..  ..   ..    ..
T(1)  T(1) ..........   ............T(1)

В этом дереве число узлов равно

2*height of tree = 2*log(n) = n

Тогда T(n) = n * 1 = n = O(n)