Tại sao hợp nhất sắp xếp trường hợp xấu nhất thời gian chạy O (n log n)?

Question

Ai đó có thể giải thích cho tôi bằng tiếng Anh đơn giản hay cách dễ dàng để giải thích nó?

Answer 1

Trên loại hợp nhất "truyền thống", mỗi loại đi qua dữ liệu sẽ tăng gấp đôi kích thước của các phần phụ được sắp xếp. Sau khi vượt qua đầu tiên, tệp sẽ được sắp xếp thành các phần có độ dài hai. Sau khi vượt qua thứ hai, chiều dài bốn. Sau đó, tám, mười sáu, vv lên đến kích thước của tập tin.

Cần phải tăng gấp đôi kích thước của các phần được sắp xếp cho đến khi có một phần bao gồm toàn bộ tệp. Nó sẽ mất hai (2) lg (N) kích thước của phần để đạt được kích thước tập tin, và mỗi vượt qua của dữ liệu sẽ mất thời gian tỷ lệ thuận với số lượng hồ sơ.

Answer 2

Điều này là do trường hợp xấu nhất hoặc trường hợp trung bình, sắp xếp hợp nhất chỉ chia mảng thành hai nửa ở mỗi giai đoạn, cung cấp thành phần lg (n) và thành phần N khác từ các phép so sánh của nó. sân khấu. Vì vậy, kết hợp nó trở thành gần O (nlg n). Không có vấn đề gì nếu là trường hợp trung bình hoặc trường hợp xấu nhất, lg (n) yếu tố luôn luôn hiện diện. Phần tử N còn lại phụ thuộc vào các so sánh được thực hiện từ các so sánh được thực hiện trong cả hai trường hợp. Bây giờ trường hợp xấu nhất là một trong đó N so sánh xảy ra cho một đầu vào N ở mỗi giai đoạn. Vì vậy, nó sẽ trở thành một O (nlg n).

Answer 3

Các Hợp nhất sắp xếp sử dụng phương pháp Phân chia và chinh phục để giải quyết vấn đề sắp xếp. Đầu tiên, nó chia đầu vào làm đôi bằng cách sử dụng đệ quy. Sau khi chia, nó sắp xếp một nửa và hợp nhất chúng thành một đầu ra được sắp xếp. Xem con số

Nó có nghĩa là tốt hơn để sắp xếp một nửa của vấn đề của bạn đầu tiên và làm một chương trình con kết hợp đơn giản. Vì vậy, điều quan trọng là phải biết sự phức tạp của chương trình con hợp nhất và bao nhiêu lần nó sẽ được gọi trong đệ quy.

Mã giả cho loại hợp nhất thực sự đơn giản.

# C = output [length = N] 
# A 1st sorted half [N/2] 
# B 2nd sorted half [N/2] 
i = j = 1 
for k = 1 to n 
    if A[i] < B[j] 
     C[k] = A[i] 
     i++ 
    else 
     C[k] = B[j] 
     j++ 

Nó rất dễ dàng để thấy rằng trong mỗi vòng lặp, bạn sẽ có 4 hoạt động: k ++, i ++ hoặc j ++, các lệnh if và ghi C = A | B. Vì vậy, bạn sẽ có ít hoặc bằng 4N + 2 hoạt động với độ phức tạp O (N). Vì lợi ích của bằng chứng 4N + 2 sẽ được coi là 6N, vì là đúng cho N = 1 (4N +2 < = 6N).

Vì vậy, giả sử bạn có một đầu vào với N yếu tố và giả N là một sức mạnh của 2. Tại mỗi cấp độ bạn có thêm hai lần bài toán với một đầu vào với các yếu tố nửa từ đầu vào trước đó. Điều này có nghĩa là ở cấp độ j = 0, 1, 2, ..., lgN sẽ có 2^j các biểu tượng con có độ dài đầu vào N/2^j.Số lượng các hoạt động ở từng cấp j sẽ ít hoặc bằng

2^j * 6 (N/2^j) = 6N

Quan sát rằng nó doens't vấn đề các bạn sẽ luôn có các hoạt động 6N nhỏ hơn hoặc bằng nhau.

Vì có LGN + 1 cấp, mức độ phức tạp sẽ

O (6N * (LGN + 1)) = O (6N * LGN + 6N) = O (n LGN)

Tài liệu tham khảo:

• Coursera course Algorithms: Design and Analysis, Part 1

Answer 4

Sau khi tách mảng lên sân khấu, nơi bạn có yếu tố đơn ví dụ: gọi cho họ danh sách phụ,

• ở từng giai đoạn chúng ta so sánh các yếu tố của mỗi sublist với sublist liền kề của nó. Ví dụ, [Tái sử dụng @ hình ảnh Davi của ]

  

  1. Tại Stage-1 mỗi phần tử được so sánh với một lân cận của nó, vì vậy n 2 so sánh /.
  2. Ở Giai đoạn 2, mỗi phần tử của danh sách con được so sánh với danh sách phụ liền kề, vì mỗi danh sách con được sắp xếp, điều này có nghĩa là số lượng so sánh tối đa được thực hiện giữa hai danh sách con là < = chiều dài của danh sách con tức là 2 (ở Giai đoạn- 2) và 4 so sánh ở Giai đoạn-3 và 8 ở Giai đoạn-4 kể từ khi các danh sách con tiếp tục tăng gấp đôi chiều dài. Có nghĩa là số lượng so sánh tối đa ở mỗi giai đoạn = (chiều dài của danh sách con * (số danh sách con/2)) ==> n/2
  3. Như bạn đã quan sát tổng số giai đoạn sẽ là log(n) base 2 Vì vậy, tổng số độ phức tạp sẽ là == (số lần so sánh tối đa ở mỗi giai đoạn * số giai đoạn) == O ((n/2) * log (n)) ==> O (nlog (n))

Answer 5

thuật toán mergesort có ba bước:

1. Chia nhỏ bước tính toán vị trí giữa của mảng phụ và phải mất thời gian không đổi O (1).
2. Chinh phục bước đệ quy sắp xếp hai mảng phụ khoảng n/2 phần tử mỗi.
3. Kết hợp bước kết hợp tổng số phần tử n tại mỗi đường chuyền yêu cầu tối đa n so sánh để lấy O (n).

Thuật toán yêu cầu xấp xỉ log log để sắp xếp một mảng các phần tử n và do đó tổng thời gian phức tạp là không rõ ràng.

Answer 6

Nhiều người trong số các câu trả lời khác là rất lớn, nhưng tôi không thấy bất kỳ đề cập đến chiều cao và sâu liên quan đến "cây merge-sort" ví dụ. Đây là một cách tiếp cận câu hỏi với rất nhiều tập trung vào cây. Dưới đây là một hình ảnh khác để giúp giải thích:

Tóm tắt lại: vì các câu trả lời khác đã chỉ ra rằng công việc sát nhập hai lát được sắp xếp của chuỗi chạy trong thời gian tuyến tính (hàm trợ giúp hợp nhất mà chúng tôi gọi từ chức năng phân loại chính).
Bây giờ nhìn vào cái cây này, nơi chúng ta có thể nghĩ về từng hậu duệ của gốc (không phải gốc) như một lời gọi đệ quy đến hàm sắp xếp, chúng ta hãy thử đánh giá lượng thời gian chúng ta dành cho mỗi nút ... cắt chuỗi và kết hợp (cả hai cùng nhau) lấy thời gian tuyến tính, thời gian chạy của bất kỳ nút nào là tuyến tính đối với độ dài của chuỗi tại nút đó.

Đây là nơi chiều sâu cây vào. Nếu n là tổng kích thước của chuỗi ban đầu, kích thước của chuỗi tại bất kỳ nút nào là n/2 ⁱ, trong đó i là độ sâu. Điều này được thể hiện trong hình trên. Đặt điều này cùng với số lượng tuyến tính của công việc cho mỗi lát, chúng tôi có một thời gian chạy của O (n/2 ⁱ) cho mỗi nút trong cây. Bây giờ chúng ta chỉ cần tính tổng cho các nút n. Một cách để làm điều này là nhận ra rằng có 2 nút ⁱ ở mỗi mức độ sâu trong cây. Vì vậy, đối với mọi cấp độ, chúng tôi có O (2 ⁱ * n/2 ⁱ), là O (n) vì chúng tôi có thể hủy bỏ 2 ⁱ s! Nếu mỗi chiều sâu là O (n), chúng ta chỉ cần nhân số đó với chiều cao của cây nhị phân này, là logn. Trả lời: O (nlogn)

tham khảo: Data Structures and Algorithms in Python