Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.4k views
in Technique[技术] by (71.8m points)

algorithm - Solving a recurrence: T(n)=3T(n/2)+n

I need to Find the solution of the recurrence for n, a power of two if T(n)=3T(n/2)+n for n>1 and T(n)=1 otherwise.

using substitution of n=2^m,S(m)=T(2^(m-1)) I can get down to:

S(m)=2^m+3*2^(m-1)+3^2*2^(m-2)+?+3^(m-1) 2^1+3^m

But I have no idea how to simply that.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

These types of recurrences are most easily solved by Master Theorem for analysis of algorithms which is explained as follows:

Let a be an integer greater than or equal to 1, b be a real number greater than 1, and c be a positive real number. Given a recurrence of the form -

T (n) = a * T(n/b) + nc where n > 1, then for n a power of b, if

  1. Logba < c, T (n) = Θ(nc);
  2. Logba = c, T (n) = Θ(nc * Log n);
  3. Logba > c, T (n) = Θ(nlogba).

English translation of your recurrence

The most critical thing to understand in Master Theorem is the constants a, b, and c mentioned in the recurrence. Let's take your own recurrence - T(n) = 3T(n/2) + n - for example.

This recurrence is actually saying that the algorithm represented by it is such that,

(Time to solve a problem of size n) = (Time taken to solve 3 problems of size n/2) + n

The n at the end is the cost of merging the results of those 3 n/2 sized problems.


Now, intuitively you can understand that:

  • if the cost of "solving 3 problems of size n/2" has more weight than "n" then the first item will determine the overall complexity;
  • if the cost "n" has more weight than "solving 3 problems of size n/2" then the second item will determine the overall complexity; and,
  • if both parts are of same weight then solving the sub-problems and merging their results will have an overall compounded weight.

From the above three intuitive understanding, only the three cases of Master Theorem arise.


In your example, a = 3, b = 2 and c = 1. So it falls in case-3 as Logba = Log23 which is greater than 1 (the value of c).

The complexity therefore is straightforward - Θ(nlogba) = Θ(nlog23).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

1.4m articles

1.4m replys

5 comments

57.0k users

...