Отношение повторения: В поисках Big O

Question

Я пытаюсь найти оценку большого O для следующего рекуррентного отношения:

T(n) = T(n-1) + n^c, where c >= 1 is a constant

Итак, я решил решить эту проблему с помощью итерации:

T(n) = T(n-1) + n^c
T(n-1) = T(n-2) + (n-1)^c
T(n) = T(n-2) + n^c + (n-1)^c
T(n-2) = T(n-3) + (n-2)^c
T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c
T(n) = T(n-k) + n^c + (n-1)^c + .... + (n-k+1)^c

Suppose k = n-1, then:

T(n) = T(1) + n^c + (n-1)^c + (n-n+1+1)^c
T(n) = n^c + (n-1)^c + 2^c + 1

Однако я не уверен, что это правильно, плюс я был бы очень признателен за некоторые рекомендации относительно того, как извлечь из этого Big O. Большое спасибо!

Answer 1

Да, вы правы:

T (n) = n ^c + (n-1) ^c + (n-2) ^c +… + 3 ^c + 2 ^c + 1,

, и эта сумма составляет

T (n) = O (n ^{c + 1} ).См. Например, формула Фолхабера .На самом деле, вы даже можете определить константу в главном члене (даже если она не имеет отношения к асимптотике алгоритма): сумма равна n ^{c + 1} / (c + 1) + O (^c ), как вы можете определить, например, используя, скажем, интеграцию.

Answer 2

То, что у вас есть, не правильно, но вы были на правильном пути.

Ошибка, которую вы сделали:

T(n) = T(n-3) + n^c + (n-1)^c + (n-2)^c    
T(n) = T(n-k) + n^c + (n-1)^c + (n-k+1)^c 

Вы не можете просто перейти с первой строки на вторую строку.

Когда вы увеличиваете k, число терминов в правой части тоже увеличивается.

Чтобы увидеть, что подумайте о написании этого так:

T(n) - T(n-1)  = n^c.

T(n-1) - T(n-2) = (n-1)^c
..

T(n-k) - T(n-k-1) = (n-k)^c.

..
T(2) - T(1) = 2^c

Чтопроизойдет, если вы сложите их?

Как только вы это сделаете, вы сможете увидеть, каким будет ответ для c = 1 и c = 2?Можете ли вы найти схему для окончательного ответа оттуда?

Answer 3

Вот оно:

T(n) = n^c + (n-1)^c + (n-2)^c + ... + 2^c + 1^c
     < n^c +     n^c +     n^c + ... + n^c + n^c
     = n * n^c
     = n^(c+1)

, который является O (n ^{c + 1} ).

Чтобы показать, что это разумный предел, обратите внимание, что когда c = 1,

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

что явно Θ (n ² ).

Answer 4

Чтобы понять это, заполните пару терминов и найдите шаблон:

T (1) = 0 + 1 ^ c

T (2) = T (1) + 2 ^ c = 0 + 1 ^ c + 2 ^ c

T (3) = T (2) + 3 ^ c = 0 + 1 ^ c + 2 ^ c + 3 ^ c

T (4) = ...

Теперь выразите шаблон через n, и у вас есть ответ.

Answer 5

Я бы начал с наблюдения, что n ^ c, хотя, конечно, под влиянием значения n, не будет более сложным для n по сравнению с n + 1 - именно c определяет "время выполнения" этого конкретногосрок.Учитывая это, вы можете предположить (по крайней мере, я бы), что термин имеет постоянное время выполнения и определить, сколько раз рекурсия будет выполняться для данного n, и вы получите свою оценку.

Answer 6

Вместо того, чтобы работать вниз с n, как насчет того, чтобы начать работать с 0 (я предполагаю, что рекурсия заканчивается на 0, а вы оставили этот бит). Когда вы начинаете замечать фиксированную точку (то есть шаблон, который повторяется во всех случаях), у вас есть хороший кандидат для ответа. Попробуйте доказать ответ, например, через индукцию.