Рекурсивный алгоритм решает рекуррентное соотношение и дает временную сложность в худшем случае, это правильно?

Question

Найти временную сложность, в худшем случае, в функции n = 2N, N> = 0.

Найдите рекуррентное отношение и решите его.

public static void xpto(v, n){ 
    if (n <= 1) 
     return; 
    n=n/2; 
    for(i=0;i<n;i=i+1) 
     v[i] = v[2i] + v[2i +1]; 
    xpto(v, n); 
} 

T(1) = 1 

уравнение рецидива по substituiton:

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

T(n) = 3 + 2n + T(n/2) 

T(n/2) = 3(2) + 2n(2) + T(n/4) 

T(n/4) = 3(3) + 2n(3) + T(n/8) 

T(n/8) = 3(4) + 2n(4) + T(n/16) 

узор найдено

T(n/8) = 3(4) + 2n(4) + T(n/2^4) 

общий рецидив в терминах K:

T(n) = 3(k) + 2n(k) + T(n/2^k) 

if T(1) = 1 and T(n/2^k) we need to change 2^k by n, this means: 

2^k = n 

T(n) = 3(log n) + 2n(log n) + 1 

Рекуррентное соотношение решена.

Временная сложность, в худшем случае O (журнал (п))

Вопросы:

• я делаю это право?
• Какая функция n = 2N, N> = 0 означает?

Answer 1

Во-первых, если вы получили: T(n) = 3(log n) + 2n(log n) + 1 в качестве окончательного решения, то наихудшая сложность не будет log n, а скорее n(log n) из-за срока 2n(log n).

Из вашего первоначального рекуррентного соотношения: T(n) = 3 + 2n + T(n/2) я сделал следующее:

Assume n = 2^k and g(k) = T(n) such that: 
g(k) = g(k-1) + 2*2^k + 3 (from simply substituting n=2^k and change of function) 
g(k) = sum(i=1 to k) of (2*2^i + 3) 
g(k) = 2 * (sum(i=1 to k) of (2^i)) + 3k 

Using geometric progression, common ratio = 2: 
g(k) = 2 * (2(1-2^k)/(1-2)) + 3k 
g(k) = -4 + 4*2^k + 3k 

Since we initially assumed n = 2^k, this means k = log n: 
T(n) = -4 + 4n + 3(log n) 
Hence the worst case complexity is O(n) 

Для второй части Вашего вопроса:

п = 2N, где N> = 0 означает просто п представляет собой набор четные числа, так как любое положительное целое число, умноженное на 2, будет четным.

Answer 2

Я не уверен, как вы получили константы, но предположим для простоты, что операция v[i] = v[2i] + v[2i +1]; стоит 1, а все остальное бесплатное. (Его можно легко отрегулировать, не навредив понятию следующих расчетов).

Исходя из этого,

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

Исходя из этого, мы можем использовать master theorem case 1 с c=1, a=1,b=2 и заключить T(n) в Theta(n^1)=Theta(n)