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

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

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

Finally, formal definitions

Cuối cùng, định nghĩa hình thức

Let f, g be positive non-decreasing functions defined on positive integers. (Note that all runtime functions satisfy these conditions.) We say that f (N) is O(g(N)) (read: f is big-oh of g) if for some c and N0 the following condition holds:

Cho f, g là các hàm dương không giảm xác định trên tập số nguyên dương. (Lưu ý rằng tất cả các hàm khi chạy phải thỏa mãn các điều kiện này). Ta nói rằng f (N) là O (g (N)) (đọc: f là độ lớn-oh của g) nếu cho c và N0 các điều kiện thỏa mãn:

$\displaystyle \forall$N > N0f (N) < c.g(N)
In human words, f (N) is O(g(N)), if for some c almost the entire graph of the function f is below the graph of the function c.g. Note that this means that f grows at most as fast as c.g does.
Nói cách tự nhiên, f (N) là O (g (N)), nếu cho c gần như toàn bộ đồ thị của hàm f là dưới đồ thị của hàm cg. Lưu ý rằng điều này có nghĩa là f tăng ở hầu hết nhanh như cg.

Instead of “f (N) is O(g(N))” we usually write f (N) = O(g(N)). Note that this “equation” is not symmetric – the notion ” O(g(N)) = f (N)” has no sense and ” g(N) = O(f (N))” doesn’t have to be true (as we will see later). (If you are not comfortable with this notation, imagine O(g(N))to be a set of functions and imagine that there is a $ \in$ instead of =.)

Thay vì “f (N) là O (g (N))” chúng ta thường viết f (N) = O (g (N)). Lưu ý rằng “phương trình” không đối xứng – khái niệm “O (g (N)) = f (N)” không có ý nghĩa và “g (N) = O (f (N))” không phải là đúng (như chúng ta sẽ thấy sau này). (Nếu bạn không thoải mái với ký hiệu này, hãy tưởng tượng O (g (N)) là một tập hợp các hàm và tưởng tượng rằng có một $ \ in $ thay vì =.)

What we defined above is known as the big-oh notation and is conveniently used to specify upper bounds on function growth.

Những gì chúng ta định nghĩa ở trên được gọi là các ký hiệu lớn-oh và thuận tiện dùng để xác định giới hạn trên đối với hàm tăng.

E.g. consider the function f (N) = 3N(N – 1)/2 + N = 1.5N2 – 0.5N from Example 2. We may say that f (N) = O(N2) (one possibility for the constants is c = 2 and N0 = 0). This means thatf doesn’t grow (asymptotically) faster than N2.

Ví dụ xem xét hàm f (N) = 3N (N – 1) / 2 + N = 1.5N2 – 0.5N từ Ví dụ 2. Chúng tôi có thể nói rằng f (N) = O(N2) (một khả năng cho các hằng số là c = 2 và N0 = 0). Điều này có nghĩa rằng f không tăng (tiệm cận) nhanh hơn so với N2.

Note that even the exact runtime function f doesn’t give an exact answer to the question “How long will the program run on my machine?” But the important observation in the example case is that the runtime function is quadratic. If we double the input size, the runtime will increase approximately to four times the current runtime, no matter how fast our computer is.

Lưu ý rằng ngay cả những hàm chính xác thời gian chạy f không đưa ra một câu trả lời chính xác cho câu hỏi “Chương trình chạy trên máy của tôi bao lâu?” Nhưng nhận xét quan trọng trong ví dụ là hàm thời gian chạy là bậc hai. Nếu chúng ta tăng gấp đôi kích thước đầu vào, thời gian chạy sẽ tăng khoảng bốn lần thời gian chạy hiện tại, máy tính của chúng ta nhanh đến mức nào không phải là vấn đề

The f (N) = O(N2) upper bound gives us almost the same – it guarantees that the growth of the runtime function is at most quadratic.

Giới hạn trên f (N) = O(N2) cho ta gần như giống nhau – nó đảm bảo rằng sự phát triển của các hàm thời gian chạy là tại hầu hết các bậc hai.

Thus, we will use the O-notation to describe the time (and sometimes also memory) complexity of algorithms. For the algorithm from Example 2 we would say “The time complexity of this algorithm is O(N2)” or shortly “This algorithm is O(N2)”.

Do đó, chúng tôi sẽ sử dụng ký hiệu – O để mô tả độ phức tạp thời gian (và đôi khi là bộ nhớ) của thuật toán. Đối với các thuật toán Ví dụ 2 chúng ta sẽ nói “Độ phức tạp thời gian của thuật toán này là O(N2)” hoặc ngắn hơn “thuật toán này là O(N2)”.

In a similar way we defined O we may define $ \Omega$ and $ \Theta$.

Tương tự, ta định nghĩa  $ \Omega$ and $ \Theta$.

We say that f (N) is $ \Omega$(g(N)) if g(N) = O(f (N)), in other words if f grows at least as fast as g.

Ta nói rằng f(N) là $ \Omega$(g(N)) nếu g(N) = O(f (N)), nói cách khác nếu f tăng tối thiểu nhanh như g.

We say that f (N) = $ \Theta$(g(N)) if f (N) = O(g(N)) and g(N) = O(f (N)), in other words if both functions have approximately the same rate of growth.

Ta nói rằng f (N) = $ \Theta$(g(N)) nếu f (N) = O(g(N)) và g(N) = O(f (N)), nói cách khác nếu cả hai hàm xấp xỉ cùng một tỉ lệ tăng

As it should be obvious,  \Omega is used to specify lower bounds and $ \Theta$ is used to give a tight asymptotic bound on a function. There are other similar bounds, but these are the ones you’ll encounter most of the time.

Rõ ràng, \Omega được sử dụng để xác định giới hạn dưới và \Theta được sử dụng để cung cấp cho một tiệm cận ràng buộc chặt chẽ trên hàm. Có những giới hạn tương tự khác, nhưng những cái này là những cái mà bạn sẽ gặp phải hầu hết thời gian.

Some examples of using the notation

Một vài ví dụ về việc sử dụng ký hiệu

  • 1.5N2 -0.5N = O(N2).
  • 47N log N = O(N2).
  • N log N + 1 000 047N = $ \Theta$(N log N).
  • All polynomials of order k are O(Nk).
  • Tất cả những đa thức bậc k là O(Nk).
  • The time complexity of the algorithm in Example 2 is $ \Theta$(N2).
  • Độ phức tạp thời gian của thuật toán trong ví dụ 2 là $ \Theta$(N2).
  • If an algorithm is O(N2), it is also O(N5).
  • Nếu một thuật toán là O(N2), nó cũng là O(N5)
  • Each comparision-based sorting algorithm is $ \Omega$(N log N).
  • Mỗi thuật toán sắp xếp dựa trên so sánh là $ \Omega$(N log N).
  • MergeSort run on an array with N elements does roughly N log N comparisions. Thus the time complexity of MergeSort is $ \Theta$(N log N). If we trust the previous statement, this means that MergeSort is an asymptotically optimal general sorting algorithm.
  • Mergesort chạy trên một mảng với N phần tử xấp xỉ so sánh N log N. Do đó độ phức tạp của mergesort là \Theta (N log N). Nếu chúng ta tin tưởng vào bản báo cáo trước đó, điều này có nghĩa rằng mergesort là một thuật toán sắp xếp tổng quát tiệm cận tối ưu
  • The algorithm in Example 2 uses $ \Theta$(N) bytes of memory.
  • Thuật toán trong Ví dụ 2 sử dụng $ \Theta$(N) bytes của bộ nhớ
  • The function giving my number of teeth in time is O(1).
  • A naive backtracking algorithm trying to solve chess is O(1) as the tre of positions it will examine is finite. (But of course in this case the constant hidden behind the O(1) is unbelievably large.)
  • The statement “Time complexity of this algorithm is at least O(N2)” is meaningless. (It says: “Time complexity of this algorithm is at least at most roughly quadratic.” The speaker probably wanted to say: “Time complexity of this algorithm is $ \Omega$(N2).”)

When speaking about the time/memory complexity of an algorithm, instead of using the formal$ \Theta$(f (n))-notation we may simply state the class of functions f belongs to. E.g. if f (N) = $ \Theta$(N), we call the algorithm linear. More examples:

Khi nói về độ phức tạp thời gian / bộ nhớ của một thuật toán, thay vì sử dụng chính thức ký hiệu $ \Theta$(f (n))- chúng tôi có thể chỉ đơn giản là nêu các lớp của hàm f thuộc về. Ví dụ nếu f (N) = \ Theta (N), chúng ta gọi là thuật toán tuyến tính. Nhiều ví dụ:

  • f (N) = $ \Theta$(log N): logarithmic
  • f (N) = $ \Theta$(N2): quadratic
  • f (N) = $ \Theta$(N3): cubic
  • f (N) = O(Nk) for some k: polynomial
  • f (N) = $ \Omega$(2N): exponential

For graph problems, the complexity $ \Theta$(N + M) is known as “linear in the graph size”.

Determining execution time from an asymptotic bound

For most algorithms you may encounter in praxis, the constant hidden behind the O (or $ \Theta$) is usually relatively small. If an algorithm is $ \Theta$(N2), you may expect that the exact time complexity is something like 10N2, not 107N2.

The same observation in other words: if the constant is large, it is usually somehow related to some constant in the problem statement. In this case it is good practice to give this constant a name and to include it in the asymptotic notation.

An example: The problem is to count occurences of each letter in a string of N letters. A naive algorithm passes through the whole string once for each possible letter. The size of alphabet is fixed (e.g. at most 255 in C), thus the algorithm is linear in N. Still, it is better to write that its time complexity is $ \Theta$(| S|.N), where S is the alphabet used. (Note that there is a better algorithm solving this problem in $ \Theta$(| S| + N).)

In a TopCoder contest, an algorithm doing 1 000 000 000 multiplications runs barely in time. This fact together with the above observation and some experience with TopCoder problems can help us fill the following table:

complexity maximum N
$ \Theta$(N) 100 000 000
$ \Theta$(N log N) 40 000 000
$ \Theta$(N2) 10 000
$ \Theta$(N3) 500
$ \Theta$(N4) 90
$ \Theta$(2N) 20
$ \Theta$(N!) 11
Table 3. Approximate maximum problem size solvable in 8 seconds.

 

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: