The solution of the recurrence relation: T (n) = T (n-1) + T (n / 2) + n

Decide: T (n) = T (n-1) + T (n / 2) + n .

I tried to solve this using recursion trees. There are two branches T(n-1)and T(n/2)respectively. T(n-1)will go to a higher depth. So, we get O(2^n). Is this idea correct?

+4
source share
4 answers

No, your idea is wrong. Complexity O(n)must also acknowledge that this problem is complex.

Here is the solution. T(n) = T(n-1) + T(n/2) + n. Since you are calculating things for very large nthan n-1almost the same as n. Therefore, you can rewrite it asT(n) = T(n) + T(n/2) + n

, :

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

: , a < 1.

.

enter image description here

, . , - , , . , T(1) = b. , n/2^k = 1 n = 2^k, , k = log n.

k , , O(n), .

,

T(n/2) + n = 0, T(n) = - 2n, . ( ), , , T(n)=T(n-1)+T(n/2)+n - -2n - 2.

, , n 1. , O(n)

P.S. , CS.

+5

, . : (-1) (/2). , , n-1 , n/2, , , n-1 . , big-o " ", , n-1 ( , ). , n , , O (2 ^ n).

+1

, . (, , 2x^3+4=O(2^n), , 2x^3+4=O(x^3).)

, , n. , T(n)=an+b. , :

an+b = a(n-1)+b + an/2+b + n

0 = (a/2+1)n + (b-a)

, a=-2 b=a=-2. T(n)=-2n-2 .

, . U(n)=T(n)+2n+2.

U(n)-2n-2 = U(n-1)-2(n-1)-2 + U(n/2)-2(n/2)-2 + n

U(n) = U(n-1) + U(n/2).

U(n)=0 , ?

, U(n)∈Θ(n^k) k>0, U(n)=cn^k+o(n^k).

cn^k+o(n^k) = c(n-1)^k+o((n-1)^k) + c(n/2)^k+o((n/2)^k)

(n-1)^k=n^k+Θ(n^{k-1}),

cn^k+o(n^k) = cn^k+Θ(cn^{k-1})+o(n^k+Θ(n^{k-1})) + cn^k/2^k+o((n/2)^k)

cn^k,

o(n^k) = cn^k/2^k

, , . , U(n-1)+U(n/2) , U(n), , U(n) , Θ(n^k). k, U(n) , .

, , . , , U(n)∈Θ(c^n) c>1, U(n)=ac^n+o(c^n). ac ^ n + o (c ^ n) = ac ^ {n-1} + o (c ^ {n-1}) + ac ^ {n/2} + o (c ^ {n/2}) ,

c^n = o(c^n)

(), , . , U(n) , U(n-1)+U(n/2), , U(n) , Θ(c^n). c>1, U(n) .

, ln U(n)∈O(log^c n) , ln U(n)∈O(n^ε). , L(n):=ln U(n), , L(n)∈ω(ln n)∩o(n). ,

ln U(n) = ln( U(n-1) + U(n/2) ) = ln U(n-1) + ln(1+ U(n/2)/U(n-1))

L(n) = L(n-1) + ln( 1 + e^{-L(n-1)+L(n/2)} ) = L(n-1) + e^{-(L(n-1)-L(n/2))} + Θ(e^{-2(L(n-1)-L(n/2))})

, : L(n-1)-L(n/2)? , L(n-1)-L(n/2)→∞, L(n)∈Ω(n). , L(n)-L(n/2) , L(n)-L(n-1)∈o(1) L(n-1)-L(n/2).

, , . , L(n)-L(n/2) ( ). , , : " CS-".

0

T(n)=T(n-1)+T(n/2)+n T(n)=T(n)+T(n/2)+n, n. T(n)=T(n)+T(n/2)+n , T(n/2) + n = 0. T(n) = T(n) + 0 ~= O(n)

-3

Source: https://habr.com/ru/post/1608145/


All Articles