Nghiên cứu về độ phức tạp của thuật toán (phần 5)

· Thuật toán, Tin học, Uncategorized

Trích từ trang web : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1

In this part of the article we will focus on estimating the time complexity for recursive programs. In essence, this will lead to finding the order of growth for solutions of recurrence equations. Don’t worry if you don’t understand what exactly is a recurrence solution, we will explain it in the right place at the right time. But first we will consider a simpler case – programs without recursion.

Nested loops

First of all let’s consider simple programs that contain no function calls. The rule of thumb to find an upper bound on the time complexity of such a program is:

  • estimate the maximum number of times each loop can be executed,
  • add these bounds for cycles following each other.
  • multiply these bounds for nested cycles/parts of code,

Example 1. Estimating the time complexity of a random piece of code.

 

int result=0;                           //  1
for (int i=0; i<N; i++)                 //  2
  for (int j=i; j<N; j++) {             //  3
    for (int k=0; k<M; k++) {           //  4
      int x=0;                          //  5
      while (x<N) { result++; x+=3; }   //  6
    }                                   //  7
    for (int k=0; k<2*M; k++)           //  8
      if (k%7 == 4) result++;           //  9
  }                                     // 10

The time complexity of the while-cycle in line 6 is clearly O(N) – it is executed no more than N/3  + 1 times.

Now consider the for-cycle in lines 4-7. The variable k is clearly incremented O(M) times. Each time the whole while-cycle in line 6 is executed. Thus the total time complexity of the lines 4-7 can be bounded by O(MN).

The time complexity of the for-cycle in lines 8-9 is O(M). Thus the execution time of lines 4-9 is O(MN + M) =O(MN).

This inner part is executed O(N2) times – once for each possible combination of i and j. (Note that there are only N(N+ 1)/2 possible values for [ij]. Still, O(N2) is a correct upper bound.)

From the facts above follows that the total time complexity of the algorithm in Example 1 is O(N2.MN) = O(MN3).

From now on we will assume that the reader is able to estimate the time complexity of simple parts of code using the method demonstrated above. We will now consider programs using recursion (i.e. a function occasionally calling itself with different parameters) and try to analyze the impact of these recursive calls on their time complexity.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: