Bagaimana cara menggunakan argumen musuh untuk seleksi dan penyisipan?

Saya diminta untuk menemukan argumen musuh yang diperlukan untuk menemukan batas bawah untuk seleksi dan jenis penyisipan. Saya tidak dapat menemukan referensi di mana pun.

Saya ragu tentang ini. Saya mengerti bahwa argumen musuh biasanya digunakan untuk menemukan batas bawah untuk "masalah" tertentu daripada "algoritma".

Saya mengerti masalah penggabungan. Tapi bagaimana saya bisa menulis satu untuk seleksi dan penyisipan?

Dari komentar Anda, tampaknya Anda membingungkan arti batas bawah, batas atas, dan notasi asimptotik. Misalnya, ambil Jenis Penyisipan. Waktu terbaik untuk menjalankannya adalah$\Theta(n)$(ini terjadi ketika input sudah diurutkan). Waktu lari terburuknya adalah$\Theta(n^2)$(ini terjadi ketika input dalam urutan terbalik). Jadi, karena waktu berjalan jatuh di antara fungsi linier dari$n$ dan fungsi kuadrat dari $n$, Anda dapat mengatakan bahwa waktu berjalan Sortasi Penyisipan adalah keduanya $\Omega(n)$ dan $O(n^2)$. Penting untuk dipahami dalam kasus ini bahwa Anda tidak dapat mengatakan bahwa waktu yang diperlukan sedang berjalan$\Omega(n^2)$. Mengapa? Karena ada input yang menyebabkan algoritma berjalan$O(n)$. Namun, Anda dapat mengatakan bahwa waktu tayang terburuk adalah$\Omega(n^2)$, lagi karena ada input yang menyebabkan algoritma berjalan $\Omega(n^2)$. Kami biasanya menggunakan$O$ notasi untuk kasus terburuk, karena kami tertarik pada batas atas pada jumlah operasi yang dilakukan oleh algoritma.

Sekarang, mari kita pikirkan argumen musuh untuk Sortasi Penyisipan (Anda dapat mencoba untuk mendapatkan satu untuk Sort Sortir dengan menerapkan ide yang sama).

Pertimbangkan algoritme Penyisipan yang dimainkan melawan lawan yang akan kita sebut lawan. Tujuan dari musuh adalah untuk memberikan input X untuk algoritma yang memaksimalkan jumlah perbandingan yang dilakukan oleh algoritma. Ini biasanya dianalisis dalam konteks pohon keputusan . Pohon keputusan menunjukkan semua urutan perbandingan yang mungkin dilakukan algoritma. Setiap simpul interior pohon keputusan mewakili perbandingan tunggal. Dua anak simpul mewakili dua hasil perbandingan (ya / tidak atau benar / salah). Setiap daun mewakili kemungkinan hasil. Untuk menyortir algoritma, daun adalah permutasikunci. Algoritme dimulai pada root dan mengikuti jalan ke daun. Pada setiap simpul internal, jawaban untuk perbandingan yang dilakukan memberitahu algoritma simpul mana yang harus dikunjungi berikutnya. Ketika algoritma mencapai daun, itu menghasilkan permutasi yang sesuai. Waktu berjalan suatu algoritma (dilihat sebagai pohon keputusan) untuk input yang diberikan adalah jumlah perbandingan yang dilakukan di jalur dari root ke daun output. Sekarang, musuh memiliki strategi sederhana yang akan bekerja terhadap setiap algoritma pengurutan berbasis perbandingan, termasuk Jenis Penyisipan: setiap kali algoritma membuat perbandingan, musuh memilih jawaban yang akan menghilangkan permutasi sesedikit mungkin.

Secara umum, karena fakta bahwa dengan $n$ elemen ada $n!$ kemungkinan permutasi, setiap pohon keputusan untuk menyortir harus memiliki setidaknya $n!$ daun, dan karenanya harus memiliki kedalaman $\Omega(\log(n!)) = \Omega(n\log n)$(dengan perkiraan Stirling). Untuk Penyisipan Sortir, musuh dapat membuat input tertentu yang menyebabkan pohon keputusan yang sesuai memiliki kedalaman setidaknya$\Omega(n^2)$.

Algoritma menggunakan array $A[1 .. n]$ untuk menyimpan elemen input dan didasarkan pada invarian berikut:

Pada awal setiap iterasi for for, subarray $A[1 .. j-1]$ terdiri dari elemen - elemen yang aslinya dalam $A[1 .. j-1]$, tetapi dalam urutan.

Dalam setiap iterasi, elemen dalam $A[1 .. j-1]$ Oleh karena itu sudah dalam urutan, dan algoritma memeriksa $A[j]$ dan menyisipkannya di tempat terakhir yang layak, dengan membandingkan nilai $A[j]$ terhadap nilai elemen dalam $A[1 .. j-1]$, mulai dari $A[j-1]$ dan melanjutkan kembali ke $A[j-2]$ dan seterusnya sampai $A[j]$bukan lagi yang terbesar dalam perbandingan. Elemen dalam$A[j+1 .. n]$ berada dalam kondisi yang tidak diketahui (berkenaan dengan urutan pengurutan) dan akan diproses dalam iterasi selanjutnya.

Inilah strategi musuh. Mengetahui bahwa algoritme berfungsi dengan menyisipkan$A[j]$ di tempat yang tepat dengan memindahkan elemen dalam $A[1 .. j-1]$, maka strategi yang jelas adalah memaksimalkan dalam $j$-Iterasi jumlah elemen yang harus dipindahkan untuk mengakomodasi $A[j]$. Ini mudah dilakukan dengan memilih input dengan hati-hati sehingga urutannya terbalik . Memang, dalam hal ini, jumlah elemen yang harus dipindahkan dalam setiap iterasi adalah$j-1$. Ini mengarah pada$\Omega(n^2)$ waktu lari terburuk (ditentukan oleh seri aritmatika yang sesuai).