Смущен на повторение и 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)