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

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

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

What is efficiency?

Hiệu quả là gì ?

Example 2. Suppose you have a concrete implementation of some algorithm. (The example code presented below is actually an implementation of MinSort – a slow but simple sorting algorithm.)

Ví dụ 2. Giả sử bạn đang có một thuật toán cụ thể. (Thuật toán được trình bày dưới đây là MinSort -. Một thuật toán sắp thứ tự lâu nhưng đơn giản)

for (int i=0; i<N; i++)
  for (int j=i+1; j<N; j++)
    if (A[i] > A[j])
      swap( A[i], A[j] );

If we are given an input to this algorithm (in our case, the array A and its size N), we can exactly compute the number of steps our algorithm does on this input. We could even count the processor instructions if we wanted to. However, there are too many possible inputs for this approach to be practical.

Nếu ta cho đầu vào cho thuật toán này (mảng A gồm N phần tử), ta có thể tính toán chính xác số lượng các bước thuật toán thực hiện trên đầu vào này. Ta thậm chí có thể đếm các lệnh xử lý nếu muốn. Tuy nhiên, có quá nhiều đầu vào có thể cho cách tiếp cận này là khả thi

And we still need to answer one important question: What is it exactly we are interested in? Most usually it is the behavior of our program in the worst possible case – we need to look at the input data and to determine an upper bound on how long will it take if we run the program.

Và ta vẫn cần phải trả lời một câu hỏi quan trọng: chính xác là ta quan tâm đến điều gì? Thông thường đó là hành vi của chương trình trong trường hợp xấu nhất có thể – ta cần phải nhìn vào các dữ liệu đầu vào và xác định một giới hạn trên của thời gian ta chạy chương trình

But then, what is the worst possible case? Surely we can always make the program run longer simply by giving it a larger input. Some of the more important questions are: What is the worst input with 700 elements? How fast does the maximum runtime grow when we increase the input size?

Vậy, trường hợp xấu nhất có thể là gì? Chắc chắn ta có thể làm cho chương trình chạy lâu hơn bằng cách cho nó một đầu vào lớn hơn.

Một số câu hỏi quan trọng hơn là:

Đầu vào xấu nhất với 700 phần tử là gì?

Thời gian chạy tối đa tăng nhanh như thế nào khi ta tăng kích thước đầu vào?

Formal notes on the input size

Những chú ý hình thức về kích cỡ đầu vào

What exactly is this “input size” we started to talk about? In the formal definitions this is the size of the input written in some fixed finite alphabet (with at least 2 “letters”). For our needs, we may consider this alphabet to be the numbers 0..255. Then the “input size” turns out to be exactly the size of the input file in bytes.

“Kích thước đầu vào” chúng ta bắt đầu nói, chính xác nó là gì vậy? Trong định nghĩa hình thức nó là kích cỡ của đầu vào được viết trong một số bảng chữ cái hữu hạn cố định (với ít nhất 2 “chữ cái”). Đối với nhu cầu của chúng tôi, ta có thể xem xét bảng chữ cái này là con số 0 .. 255. Khi đó “kích thước đầu vào” hóa ra là kích thước chính xác của file input trong byte.

Usually a part of the input is a number (or several numbers) such that the size of the input is proportional to the number.

Thông thường một phần của đầu vào là một số (hoặc một vài số) sao cho kích thước của đầu vào là tỷ lệ thuận với số .

E.g. in Example 2 we are given an int N and an array containing N ints. The size of the input file will be roughly 5N (depending on the OS and architecture, but always linear in N).

Ví dụ trong ví dụ 2 ta có được một số nguyên N và một mảng chứa N số nguyên. Kích thước của tập tin đầu vào sẽ xấp xỉ 5N (tùy thuộc vào hệ điều hành và kiến trúc, nhưng luôn luôn là tuyến tính trong N).

In such cases, we may choose that this number will represent the size of the input. Thus when talking about problems on arrays/strings, the input size is the length of the array/string, when talking about graph problems, the input size depends both on the number of vertices (N) and the number of edges (M), etc.

Trong trường hợp này, chúng ta có thể chọn con số này sẽ đại diện cho kích thước của đầu vào. Vì vậy, khi nói về vấn đề trên mảng /xâu, kích thước đầu vào là chiều dài của mảng /xâu, khi nói về vấn đề biểu đồ, kích thước đầu vào phụ thuộc cả vào số đỉnh (N) và số cạnh (M), v v

We will adopt this approach and use N as the input size in the following parts of the article.

Chúng tôi sẽ áp dụng phương pháp này và sử dụng N như là kích thước đầu vào trong các phần sau của bài viết.

There is one tricky special case you sometimes need to be aware of. To write a (possibly large) number we need only logarithmic space. (E.g. to write 123456, we need only roughlylog10(123456) digits.) This is why the naive primality test does not run in polynomial time – its runtime is polynomial in the size of the number, but not in its number of digits! If you didn’t understand the part about polynomial time, don’t worry, we’ll get there later.

Có một trường hợp đặc biệt khó khăn đôi khi bạn cần phải nhận thức được. Để viết (có thể lớn) số chúng ta chỉ cần không gian logarit. (Ví dụ, để viết 123456, chúng ta chỉ cần xấp xỉ log10 (123456) chữ số.) Đây là lý do tại sao kiểm tra tính nguyên ngây thơ không chạy trong thời gian đa thức – thời gian chạy của nó là đa thức trong kích thước của số lượng, nhưng không phải trong số lượng các chữ số! Nếu bạn không hiểu được một phần về thời gian đa thức, đừng lo lắng, chúng tôi sẽ đến đó sau.

How to measure efficiency?

Làm thế nào để đo lường sự hiệu quả?

We already mentioned that given an input we are able to count the number of steps an algorithm makes simply by simulating it. Suppose we do this for all inputs of size at most N and find the worst of these inputs (i.e. the one that causes the algorithm to do the most steps). Let f(N) be this number of steps. We will call this function the time complexity, or shortly the runtime of our algorithm.

Ta đã đề cập rằng cho một đầu vào ta có thể đếm số bước một thuật toán làm chỉ đơn giản là bằng cách mô phỏng nó. Giả sử chúng ta làm điều này cho tất cả các yếu tố đầu vào có kích thước tối đa là N và trường hợp xấu nhất của những đầu vào này (tức là trường hợp khiến thuật toán phải thực hiện hầu hết các bước). Cho f (N) là số các bước này. Ta sẽ gọi hàm này là  độ phức tạp thời gian, hoặc ngắn hơn là thời gian chạy của giải thuật của chúng ta.

In other words, if we have any input of size N, solving it will require at most f (N) steps.

Nói cách khác, nếu chúng ta có bất kỳ đầu vào kích thước N, giải quyết nó sẽ cần ít nhất f (N) bước.

Let’s return to the algorithm from Example 2. What is the worst case of size N? In other words, what array with N elements will cause the algorithm to make the most steps? If we take a look at the algorithm, we can easily see that:

Chúng ta hãy trở lại thuật toán từ Ví dụ 2. Trường hợp xấu nhất của kích thước N là gì? Nói cách khác, mảng với N phần tử sẽ khiến thuật toán làm cho hầu hết các bước nào? Nếu chúng ta hãy nhìn vào các thuật toán, chúng ta có thể dễ dàng thấy rằng:

  • the first step is executed exactly N times
  • Bước đầu tiên là thực hiện chính xác N lần
  • the second and third step are executed exactly N(N – 1)/2 times
  • Bước thứ hai và thứ ba được thực hiện chính xác N (N – 1) / 2 lần
  • the fourth step is executed at most N(N – 1)/2 times
  • Bước thứ tư được thực hiện tại hầu hết các N (N – 1) / 2 lần

Clearly, if the elements in A are in descending order at the beginning, the fourth step will always be executed. Thus in this case the algorithm makes 3N(N – 1)/2 + N = 1.5N2 – 0.5steps. Therefore our algorithm has f (N) = 1.5N2 – 0.5N.

Rõ ràng, nếu các phần tử trong A là thứ tự giảm dần ngay từ đầu, bước thứ tư sẽ luôn luôn được thực thi. Vì vậy, trong trường hợp này thuật toán làm cho 3N (N – 1) / 2 + N = 1.5N2 – 0.5N bước. Do đó, thuật toán của chúng tôi có f (N) = 1.5N2 – 0.5N.

As you can see, determining the exact function f for more complicated programs is painful. Moreover, it isn’t even necessary. In our case, clearly the -0.5N term can be neglected. It will usually be much smaller than the 1.5N2 term and it won’t affect the runtime significantly. The result “f (N) is roughly equal to 1.5N2” gives us all the information we need. As we will show now, if we want to compare this algorithm with some other algorithm solving the same problem, even the constant 1.5 is not that important.

Như bạn có thể thấy, việc xác định hàm chính xác f cho các chương trình phức tạp hơn rất vất vả. Hơn nữa, nó không cần thiết. Trong trường hợp của chúng tôi, rõ ràng số hạng -0.5N có thể được bỏ qua. Nó thường sẽ nhỏ hơn nhiều so với số hạng 1.5N2 và nó sẽ không ảnh hưởng đáng kể đến thời gian chạy. Kết quả “f (N) là tương đương với 1.5N2” cho chúng ta tất cả các thông tin cần thiết. Như chúng ta sẽ thấy bây giờ, nếu chúng ta muốn so sánh thuật toán này với một số thuật toán khác giải quyết cùng một bà, thậm chí hằng số 1,5 mà không phải là quan trọng.

Consider two algorithms, one with the runtime N2, the other with the runtime 0.001N3. One can easily see that for N greater than 1 000 the first algorithm is faster – and soon this difference becomes apparent. While the first algorithm is able to solve inputs with N = 20 000in a matter of seconds, the second one will already need several minutes on current machines.

Xem xét hai thuật toán, một với N2 thời gian chạy, khác với  0.001N3 thời gian chạy. Người ta có thể dễ dàng thấy rằng đối với N lớn hơn 1 000 thì thuật toán đầu tiên là nhanh hơn – và chẳng bao lâu sự khác biệt này trở nên rõ ràng. Trong khi các thuật toán đầu tiên là có thể giải quyết đầu vào với N = 20 000 trong một vài giây, cái thứ hai sẽ đã cần vài phút trên các máy hiện tại.

Clearly this will occur always when one of the runtime functions grows asymptotically faster than the other (i.e. when N grows beyond all bounds the limit of their quotient is zero or infinity). Regardless of the constant factors, an algorithm with runtime proportional to N2 will always be better than an algorithm with runtime proportional to N3 on almost all inputs. And this observation is exactly what we base our formal definition on.

Rõ ràng điều này sẽ luôn xảy ra  khi một trong những hàm thời gian chạy phát triển tiệm cận nhanh hơn khác (tức là khi N phát triển vượt ra vô cùng giới hạn của thương của chúng là số không hoặc vô cực). Không phụ thuộc vào hằng số, một thuật toán với thời gian chạy tỉ lệ với N2 sẽ luôn luôn là tốt hơn so với một thuật toán với thời gian chạy tỷ lệ thuận với N3 trên hầu hết các yếu tố đầu vào. Và sự nhận xét này là chính xác căn cứ vào sự định nghĩa hình thức của chúng ta!

 

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: