Kompleksitas pengurutan Penyisipan Biner untuk pertukaran dan perbandingan dalam kasus terbaik

Question

Apa yang mungkin menjadi kerumitan untuk jenis penyisipan biner? Dan berapa banyak swap dan perbandingan yang dibuat?

Ini mungkin O(n(LG n))perbandingan, tapi saya tidak yakin. Untuk kasus terburuk, ini memang N^2swap. Bagaimana dengan yang terbaik?

Answer 1

Anda dapat menulis urutan penyisipan biner dengan mudah dengan memanfaatkan fungsi bawaan seperti bisect_leftdan list.pop(..)dan 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

Tentang kasus terburuk, karena pada i-thiterasi loop, kami melakukan pencarian biner di dalam sub-array A[0..i], dengan 0<=i<n, itu harus mengambil log(i)operasi, jadi sekarang kami tahu kami harus memasukkan elemen di lokasi i1dan kami memasukkannya, tetapi penyisipan berarti kita harus mendorong semua elemen yang mengikutinya satu posisi ke kanan, dan itu setidaknya n-ioperasi (bisa lebih dari n-ioperasi tergantung pada lokasi penyisipan). Jika kita menjumlahkan hanya dua ini saja yang kita dapatkan\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(dalam perkiraan Stirling di atas log(n!)sedang digunakan)

Sekarang halaman wiki mengatakan

Sebagai aturan praktis, orang dapat berasumsi bahwa suku orde tertinggi dalam fungsi tertentu mendominasi laju pertumbuhannya dan dengan demikian menentukan urutan run-time-nya.

Jadi saya pikir kesimpulannya adalah bahwa dalam kasus terburuk, jenis penyisipan biner memiliki O(n^2)kompleksitas.

Lihat juga:

• penyisipan sortir menggunakan pencarian biner
• penyisipan sortir dengan pencarian biner
• analisis semacam penyisipan biner
• jenis dan kompleksitas penyisipan biner

Kemudian saya mencoba untuk memeriksa bagaimana kinerjanya pada daftar reversed ( n,n-1,n-2,..,1) dan alternating ( 0,n-1,1,n-2,2,n-3,...). Dan saya memasangkannya (menggunakan modul pertumbuhan korek api ) ke tingkat pertumbuhan yang berbeda, bagian ini hanyalah perkiraan. Urutan terbalik disesuaikan dengan waktu polinom, dan urutan bolak-balik disesuaikan dengan waktu kuasilinear

Kasus terbaik dijelaskan di sini . Jika daftar sudah diurutkan, bahkan jika kita tidak melakukan swap, semua pencarian biner masih dilakukan, yang mengarah ke O(n*log(n)).

Kode yang digunakan di sini tersedia di repositori ini.