Chèn nhị phân sắp xếp độ phức tạp để hoán đổi và so sánh trong trường hợp tốt nhất

Question

Độ phức tạp đối với sắp xếp chèn nhị phân là gì? Và có bao nhiêu hoán đổi và so sánh được thực hiện?

Nó có thể là O(n(LG n))so sánh, nhưng tôi không chắc. Đối với trường hợp xấu nhất, nó thực sự là N^2hoán đổi. Điều gì về tốt nhất?

Answer 1

Bạn có thể viết sắp xếp chèn nhị phân một cách dễ dàng bằng cách tận dụng các hàm tích hợp sẵn như bisect_leftvà list.pop(..)và list.insert(..):

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

Về trường hợp xấu nhất, vì khi i-thlặp lại vòng lặp, chúng tôi thực hiện tìm kiếm nhị phân bên trong mảng con A[0..i], với 0<=i<n, sẽ thực hiện các log(i)phép toán, vì vậy bây giờ chúng tôi biết chúng tôi phải chèn một phần tử tại vị trí i1và chúng tôi chèn nó, nhưng việc chèn có nghĩa là chúng ta phải đẩy tất cả các phần tử theo sau nó sang phải một vị trí, và đó là ít nhất là các n-ihoạt động (nó có thể nhiều hơn các n-ihoạt động tùy thuộc vào vị trí chèn). Nếu chúng ta chỉ tổng hợp hai điều này, chúng ta có\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(trong ước lượng của Stirling ở trên log(n!)đang được sử dụng)

Bây giờ trang wiki cho biết

Theo quy tắc ngón tay cái, người ta có thể giả định rằng số hạng cao nhất trong bất kỳ hàm nhất định nào chi phối tốc độ tăng trưởng của nó và do đó xác định thứ tự thời gian chạy của nó

Vì vậy, tôi nghĩ rằng kết luận sẽ là trong trường hợp xấu nhất, loại chèn nhị phân có O(n^2)độ phức tạp.

Xem thêm:

• sắp xếp chèn bằng cách sử dụng tìm kiếm nhị phân
• sắp xếp chèn với tìm kiếm nhị phân
• phân tích sắp xếp chèn nhị phân
• sắp xếp chèn nhị phân và độ phức tạp

Sau đó, tôi đã cố gắng kiểm tra xem nó hoạt động như thế nào trên danh sách đảo ngược ( n,n-1,n-2,..,1) và xen kẽ ( 0,n-1,1,n-2,2,n-3,...). Và tôi đã trang bị chúng (bằng cách sử dụng mô-đun diêm sinh ) với các tốc độ tăng trưởng khác nhau, phần này chỉ là một con số gần đúng. Thứ tự đảo ngược được phù hợp với thời gian đa thức và thứ tự xen kẽ được phù hợp với thời gian chuẩn tính

Trường hợp tốt nhất được giải thích ở đây . Nếu danh sách đã được sắp xếp, thì ngay cả khi chúng ta không thực hiện bất kỳ hoán đổi nào, tất cả các tìm kiếm nhị phân vẫn đang được thực hiện, điều này dẫn đến O(n*log(n)).

Mã được sử dụng ở đây có sẵn trong kho này.