Quicksort-Average-case analysis using discrete probability

· Quicksort

Average-case analysis using discrete probability

Phân tích trường hợp trung bình sử dụng xác suất rời rạc

Quicksort takes O(n log n) time on average, when the input is a random permutation. Why? For a start, it is not hard to see that the partition operation takes O(n) time.

Sắp xếp nhanh chiếm O (n log n) thời gian trung bình, khi đầu vào là một hoán vị ngẫu nhiên. Tại sao?

Để bắt đầu, nó không phải là khó để thấy rằng các hoạt động phân vùng chiếm O (n) thời gian.

In the most unbalanced case, each time we perform a partition we divide the list into two sublists of size 0 and n-1 (for example, if all elements of the array are equal). This means each recursive call processes a list of size one less than the previous list.

Trong trường hợp không cân bằng nhất, mỗi lần chúng tôi thực hiện một phân vùng chúng tôi chia danh sách thành hai danh sách con có kích thước 0 và n-1 (ví dụ, nếu tất cả các phần tử của mảng bằng nhau). Điều này có nghĩa mỗi lời gọi đệ quy xử lý một danh sách các kích thước nhỏ hơn danh sách trước đó một phần tử.

Consequently, we can make n-1 nested calls before we reach a list of size 1. This means that the call tree is a linear chain of n-1 nested calls. The ith call does O(n-i) work to do the partition, and \textstyle\sum_{i=0}^n (n-i) = O(n^2), so in that case Quicksort takes O(n^2) time. That is the worst case: given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy.[11]

Do đó, chúng ta có thể làm cho n-1 cuộc gọi lồng nhau trước khi chúng tôi đạt được một danh sách có kích thước 1. Điều này có nghĩa rằng các cây gọi là một chuỗi tuyến tính của n-1 cuộc gọi lồng nhau. Lời gọi thứ i thực hiện O (n-i) bước để làm phân vùng, và \textstyle\sum_{i=0}^n (n-i) = O(n^2)do đó trong trường hợp đó Sắp xếp nhanh O (n ^ 2) thời gian . Đó là trường hợp tồi tệ nhất: kiến thức đưa ra trong đó so sánh được thực hiện bởi sắp xếp, có những thuật toán thích ứng có hiệu quả tại tạo ra trường hợp xấu nhất đầu vào cho Sắp xếp nhanh nhanh hơn, không phụ thuộc vào chiến lược lựa chọn chốt[11].

In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size.

Trong trường hợp cân bằng nhất, mỗi lần chúng tôi thực hiện một phân vùng chúng tôi chia danh sách thành hai phần gần bằng nhau. Điều này có nghĩa mỗi cuộc gọi đệ quy xử lý một danh sách của một nửa kích thước.

Consequently, we can make only \log_2 n nested calls before we reach a list of size 1. This means that the depth of the call tree is \log_2 n. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.

Do đó, chúng tôi có thể làm chỉ \log_2 n cuộc gọi lồng nhau trước khi chúng tôi đạt được một danh sách kích thước 1. Điều này có nghĩa rằng độ sâu của cây gọi là \log_2 n. Nhưng không có hai cuộc gọi cùng cấp của quá trình cây gọi cùng một phần của danh sách ban đầu, do đó, mỗi cấp độ của các cuộc gọi chỉ cần O (n) thời gian tất cả cùng nhau (mỗi cuộc gọi có một số chi phí không đổi, nhưng kể từ khi có chỉ O (n) gọi ở mỗi cấp, điều này được gộp vào trong hệ số O (n)). Kết quả là các thuật toán chỉ sử dụng O (n log n) thời gian.

In fact, it’s not necessary to be perfectly balanced; even if each pivot splits the elements with 75% on one side and 25% on the other side (or any other fixed fraction), the call depth is still limited to \log_{4/3} n, so the total running time is still O(n log n).

Trong thực tế, nó không phải là cần thiết để có hoàn toàn cân bằng, thậm chí nếu mỗi trục chia tách các yếu tố với 75% ở một bên và 25% ở phía bên kia (hoặc bất kỳ phần cố định khác), độ sâu cuộc gọi vẫn còn hạn chế để \log_{4/3} n, vì vậy tổng thời gian chạy vẫn là O (n log n).

So what happens on average? If the pivot has rank somewhere in the middle 50 percent, that is, between the 25th percentile and the 75th percentile, then it splits the elements with at least 25% and at most 75% on each side. If we could consistently choose a pivot from the two middle 50 percent, we would only have to split the list at most \log_{4/3} n times before reaching lists of size 1, yielding an O(n log n) algorithm.

Vì vậy, những gì xảy ra trên trung bình? Nếu chốt đã xếp hạng nào đó ở giữa 50 phần trăm, đó là, giữa phần trăm và 25 phần trăm thứ 75, sau đó nó chia tách các yếu tố có ít nhất 25% và nhiều nhất là 75% trên mỗi bên. Nếu chúng ta luôn có thể chọn một trục từ hai giữa 50 phần trăm, chúng ta sẽ chỉ phải chia danh sách ở hầu hết \log_{4/3} n lần trước khi danh sách đạt kích thước 1, năng suất một O (n log n) thuật toán.

When the input is a random permutation, the pivot has a random rank, and so it is not guaranteed to be in the middle 50 percent. However, when we start from a random permutation, in each recursive call the pivot has a random rank in its list, and so it is in the middle 50 percent about half the time. That is good enough.

Khi đầu vào là một hoán vị ngẫu nhiên, chốt có một thứ hạng ngẫu nhiên, và do đó, nó không được đảm bảo để được ở giữa 50 phần trăm. Tuy nhiên, khi chúng tôi bắt đầu từ một hoán vị ngẫu nhiên, trong mỗi cuộc gọi đệ quy chốt có một thứ hạng ngẫu nhiên trong danh sách của mình, và vì vậy nó là ở giữa 50 phần trăm khoảng một nửa thời gian. Đó là đủ tốt.

Imagine that you flip a coin: heads means that the rank of the pivot is in the middle 50 percent, tail means that it isn’t. Imagine that you are flipping a coin over and over until you get k heads. Although this could take a long time, on average only 2k flips are required, and the chance that you won’t get k heads after 100k flips is highly improbable (this can be made rigorous using Chernoff bounds). By the same argument, Quicksort’s recursion will terminate on average at a call depth of only 2 \log_{4/3} n.

Hãy tưởng tượng rằng bạn lật một đồng xu: đầu có nghĩa là thứ hạng của chốt là ở giữa 50 phần trăm, đuôi nghĩa là không phải. Hãy tưởng tượng rằng bạn đang lật một đồng xu lại và lại lần nữa cho đến khi bạn có được k đầu. Mặc dù điều này có thể mất một thời gian dài, trung bình chỉ 2k lật được yêu cầu, và các cơ hội mà bạn sẽ không nhận được k đầu sau 100k lật là khô ng thể xảy ra cao hơn(điều này có thể được thực hiện nghiêm ngặt sử dụng Chernoff giới hạn). Bởi cùng một lý lẽ, đệ quy Sắp xếp nhanh sẽ chấm dứt trên trung bình ở độ sâu cuộc gọi chỉ có 2 \log_{4/3} n

 

But if its average call depth is O(log n), and each level of the call tree processes at most n elements, the total amount of work done on average is the product, O(n log n). Note that the algorithm does not have to verify that the pivot is in the middle half—if we hit it any constant fraction of the times, that is enough for the desired complexity.

Nhưng nếu chiều sâu cuộc gọi trung bình của nó là O (log n), và mỗi cấp độ của các quá trình cây gọi ở hầu hết n phần tử, tổng số lượng công việc thực hiện trên trung bình là sản phẩm, O (n log n). Lưu ý rằng các thuật toán không phải xác minh rằng các trục ở giữa nửa nếu chúng ta đặt đưa nó vào bất kỳ phần không đổi của thời gian (số lần), đó là đủ cho sự phức tạp mong muốn.

 

3 phản hồi

Comments RSS
  1. dangtrungkien

    Tớ cảm thấy mình quá bé nhỏ sau khi dịch xong cái bài này. Tớ nghĩ đến bàn cờ, đến câu chuyện cấp số nhân cấp số cộng, đến việc rải thóc mà dày vài mm, đến logarit đến hàm đa thức, hàm lũy thừa, đến cái nguyện ước nhỏ bé của con người đó là thời gian!

  2. dangtrungkien

    Một cảm giác hạnh phúc sau khi dịch xong. Một cảm giác sống phải kỷ luật kỷ luật hơn nữa, trách nhiệm hơn nữa!

  3. dangtrungkien

    Tớ vẫn còn những khát khao mãnh liệt lắm. Tớ cần phải thay đổi. Thay đổi để tuổi 24 không trở thành 80!

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: