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

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

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

A note on algorithm analysis

Usually if we present an algorithm, the best way to present its time complexity is to give a $ \Theta$-bound. However, it is common practice to only give an O-bound – the other bound is usually trivial, O is much easier to type and better known. Still, don’t forget that O represents only an upper bound. Usually we try to find an O-bound that’s as good as possible.

Example 3. Given is a sorted array A. Determine whether it contains two elements with the difference D. Consider the following code solving this problem:

Ví dụ 3. Cho một mảng A đã sắp thứ tự. sắp xếp. Xác định xem nó có chứa hai phần tử với cách biệt D. Xét đoạn mã sau giải quyết vấn đề này:

int j=0;
for (int i=0; i<N; i++) {
  while ( (j<N-1) && (A[i]-A[j] > D) )
    j++;
  if (A[i]-A[j] == D) return 1;
}

It is easy to give an O(N2) bound for the time complexity of this algorithm – the inner while-cycle is called N times, each time we increase j at most N times. But a more careful analysis shows that in fact we can give an O(N) bound on the time complexity of this algorithm – it is sufficient to realize that during the whole execution of the algorithm the command “j++;” is executed no more than N times.

Dễ thấy độ phức tạp thời gian của thuật toán này là O(N2) – trong khi chu kỳ bên trong được gọi là N lần, mỗi lần chúng ta tăng j ở hầu hết N lần. Nhưng một phân tích cẩn thận hơn cho thấy rằng trong thực tế chúng ta có thể đưa ra một giới hạn O (N) độ phức tạp của thuật toán này – đủ để nhận ra rằng trong toàn bộ thực hiện các thuật toán lệnh “j + +;” được thực hiện không quá N lần.

If we said “this algorithm is O(N2)”, we would have been right. But by saying “this algorithm isO(N)” we give more information about the algorithm.

Nếu chúng ta nói “thuật toán này là O(N2)”, ta nói đúng. Nhưng bằng cách nói “thuật toán này O (N)” chúng tôi cung cấp thêm thông tin về các thuật toán.

Conclusion

Kết luận

We have shown how to write bounds on the time complexity of algorithms. We have also demonstrated why this way of characterizing algorithms is natural and (usually more-or-less) sufficient.

Ta đã thấy làm thế nào để viết giới hạn về độ phức tạp của thuật toán. Ta cũng đã chứng minh tại sao cách này đặc trưng cho các thuật toán là tự nhiên và (thường là hơn hoặc ít hơn) đầy đủ.

The next logical step is to show how to estimate the time complexity of a given algorithm. As we have already seen in Example 3, sometimes this can be messy. It gets really messy when recursion is involved. We will address these issues in the second part of this article.

Bước tiếp theo là xem ước tính độ phức tạp của một thuật toán cho trước như thế nào. Như chúng ta đã thấy trong ví dụ 3, đôi khi điều này có thể lộn xộn. Nó thực sự lộn xộn khi có đệ quy. Ta sẽ giải quyết những vấn đề này trong phần thứ hai của bài viết này.

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: