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

· 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 article I’ll try to introduce you to the area of computation complexity. The article will be a bit long before we get to the actual formal definitions because I feel that the rationale behind these definitions needs to be explained as well – and that understanding the rationale is even more important than the definitions alone.

Bài viết này tôi sẽ giới thiệu với bạn lĩnh vực độ phức tạp tính toán. Bài viết sẽ hơi dài trước khi đến được với các định nghĩa hình thức. Bởi vì tôi thấy rằng các lý luận đằng sau những định nghĩa cần phải được giải thích – và sự hiểu biết các lý luận đó thậm chí còn quan trọng hơn các định nghĩa!

Why is it important?

Tại sao điều đó lại quan trọng?

Example 1. Suppose you were assigned to write a program to process some records your company receives from time to time. You implemented two different algorithms and tested them on several sets of test data. The processing times you obtained are in Table 1.

Ví dụ 1. Giả sử bạn viết chương trình để xử lý một số hồ sơ công ty của bạn nhận được theo thời gian. Bạn thực hiện hai thuật toán khác nhau và thử nghiệm chúng trên nhiều bộ dữ liệu thử nghiệm. Thời gian thực hiện bạn thu được trong Bảng 1.

thuat12

In praxis, we probably could tell which of the two implementations is better for us (as we usually can estimate the amount of data we will have to process). For the company this solution may be fine. But from the programmer’s point of view, it would be much better if he could estimate the values in Table 1 before writing the actual code – then he could only implement the better algorithm.

Trong thực tế, ta nói cái nào trong hai thuật toán là tốt hơn với chúng ta (khi ta ước tính lượng dữ liệu ta sẽ phải xử lý). Đối với công ty cách này có thể tốt. Nhưng theo quan điểm của lập trình viên, sẽ là tốt nhất nếu có thể ước tính giá trị trong bảng 1 trước khi viết mã thực tế – khi đó anh ta chỉ có thể thực hiện thuật toán tốt nhất.

This leads us to the question: How to compare algorithms? Before we answer this question in general, let’s return to our simple example. If we extrapolate the data in Table 1, we may assume that if the number of processed records is larger than 1000, algorithm 2 will be substantially faster. In other words, if we consider all possible inputs, algorithm 2 will be better for almost all of them.

Điều này dẫn chúng ta đến câu hỏi: So sánh các thuật toán như thế nào? Trước khi chúng tôi trả lời câu hỏi này tổng quát, chúng ta hãy quay trở lại ví dụ đơn giản của chúng tôi. Nếu chúng ta sua luận các dữ liệu trong bảng 1, chúng ta có thể giả định rằng nếu số lượng hồ sơ xử lý lớn hơn 1000, thuật toán 2 sẽ nhanh hơn đáng kể. Nói cách khác, nếu chúng ta xem xét tất cả các yếu tố đầu vào có thể, thuật toán 2 sẽ tốt hơn cho hầu hết tất cả trường hợp

It turns out that this is almost always the case – given two algorithms, either one of them is almost always better, or they are approximately the same. Thus, this will be our definition of a better algorithm. Later, as we define everything formally, this will be the general idea behind the definitions.

Điều này luôn luôn đúng- cho hai thuật toán, hoặc một trong số chúng tốt hơn, hoặc chúng xấp xỉ như nhau. Vì vậy, điều này sẽ xác định cho chúng ta về một thuật toán tốt hơn. Sau đó, khi chúng ta xác định tất cả mọi thứ hình thức, đây sẽ là ý tưởng chung đằng sau các định nghĩa.

A neat trick

Một thủ thuật tinh vi

If you thing about Example 1 for a while, it shouldn’t be too difficult to see that there is an algorithm with runtimes similar to those in Table 2:

Nếu bạn nghĩ về Ví dụ 1 một lát, không phải quá khó khăn để thấy rằng có một thuật toán với thời gian chạy tương tự như trong Bảng 2:

# of records 10 20 50 100 1000 5000
algorithm 3 0.00s 0.01s 0.05s 0.11s 0.78s 14.22s
Table 2. Runtimes of a new fictional algorithm.
Bảng 2. Thời gian c hạy của một thuật toán mới

The idea behind this algorithm: Check the number of records. If it is small enough, run algorithm 1, otherwise run algorithm 2.

 Ý tưởng đằng sau thuật toán này: Kiểm tra số hồ sơ. Nếu nó đủ nhỏ, chạy thuật toán 1, nếu không chạy thuật toán 2.

Similar ideas are often used in praxis. As an example consider most of the sort() functions provided by various libraries. Often this function is an implementation of QuickSort with various improvements, such as:

Ý tưởng tương tự thường được sử dụng trong thực hành. Một ví dụ là xét các hàm sort() được cung cấp bởi các thư viện khác nhau. Thường hàm này được thực hiện bởi Quicksort với nhiều cải tiến, chẳng hạn như:

  • if the number of elements is too small, run InsertSort instead (as InsertSort is faster for small inputs)
  • Nếu số phần tử quá nhỏ, chạy InsertSort (InsertSort nhanh hơn cho đầu vào nhỏ)
  • if the pivot choices lead to poor results, fall back to MergeSort
  • Nếu những lựa chọn đến kết quả nghèo, quay trởi lại mergesort

 

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: