Mari kita bicara tentang algoritma. Pemula sering menganggapnya sebagai sesuatu yang sulit, kompleks, dan tidak dapat dipahami, dan ini sebagian benar, tetapi algoritme adalah dasarnya. Dan semakin baik Anda mengetahui dasar-dasar spesialisasi Anda, semakin besar kemungkinan Anda untuk unggul di dalamnya.
Hari ini kita akan melihat satu masalah algoritma yang indah. Kami tidak akan menakut-nakuti orang agar tidak bekerja dengan algoritme di awal, oleh karena itu, dalam analisis kami tidak akan ada pohon segmen yang menyebar, tidak ada berbagai macam pengoptimalan masalah knapsack, atau uji probabilistik untuk kesederhanaan. Algo yang ramah pengguna.
Inilah tantangannya: temukan perbedaan maksimum di antara tetangga.
Sebuah array dari bilangan bulat N diberikan. Itu tidak diurutkan dengan cara apa pun, dan angka dapat diulang. Katakanlah kita mengurutkannya dan menghitung selisih antara setiap pasangan elemen yang berurutan. Anda perlu menemukan perbedaan maksimum dan melakukannya dengan cara yang paling optimal.
Rumit? Anda dapat mencoba melakukan ini sebelum mengklik "Baca lebih lanjut", lalu periksa solusinya.
Jadi ayo pergi. Perbedaan maksimum antar tetangga.
Pertimbangkan sebuah contoh:
Misalkan sebuah array dari N = 11 elemen diberikan.
Pertama, mari kita selesaikan masalah secara naif, ini sering kali membantu. Kita dapat melakukan persis apa yang diminta dari masalah kita - mengurutkan angka dan menemukan perbedaan antara elemen yang berdekatan. Kompleksitas solusi akan bervariasi bergantung pada penyortiran yang kami gunakan.
Jika kita menggunakan qsort atau mergesort , maka kompleksitas waktunya adalah ... Jika kita tahu bahwa angka-angka tersebut didistribusikan agak padat pada himpunan bilangan bulat, maka kita dapat menggunakan jenis penghitungan. Lalu kita dapatkan , di mana U adalah selisih antara elemen maksimum dan minimum. Kasusnya relatif jarang, tetapi perlu diingat tentang kemungkinan ini.
Setelah mengurutkan, kita mendapatkan sebuah array:
Mari kita tulis berbagai perbedaan:
Kami
mendapatkan bahwa perbedaan maksimum adalah 6. Sekarang mari kita pikirkan, apakah mungkin untuk menyelesaikan masalah dengan lebih cepat? Saat melakukan iterasi pada pasangan elemen bertetangga, kami akan mempertimbangkan banyak pasangan dengan perbedaan kecil. Pasangan seperti itu mungkin tidak akan pernah bisa memberikan perbedaan terbesar. Memang, dalam array yang diurutkan yang kita miliki sepasang angka yang berdekatan, biarkan perbedaan antara maksimum dan minimum menjadi ... Maka perbedaan terbesar harus memiliki setidaknya ... Perkiraan ini benar dengan prinsip Dirichlet.
Jika burung merpati ditempatkan dalam sangkar, dan jumlah merpati lebih banyak dari jumlah sangkar, maka minimal satu sangkar berisi lebih dari satu ekor merpati.
9 sel berisi 10 merpati, menurut prinsip Dirichlet, setidaknya satu sel berisi lebih dari satu merpati ( Wikipedia )
Biarkan , ... , - elemen ke-i dari array yang diurutkan. Kemudian ...
Jika kita mengasumsikan bahwa maksimum dari semua D [i] lebih kecil , lalu jumlah keseluruhan akan lebih kecil dari U, sebuah kontradiksi.
Hebat, kami mendapat batas bawah untuk perbedaan maksimum! Sekarang mari kita coba melokalkan elemen yang terlalu dekat satu sama lain - kita membagi segmen dari elemen minimum ke maksimum menjadi setengah interval panjang ... Setiap elemen akan jatuh tepat ke dalam satu setengah interval. Kami mendapatkan partisi dari semua elemen ke dalam grup terpisah, mereka juga disebut batch.
Sangat mudah untuk menentukan di mana elemen x berada - Anda perlu menghitung 1 + int ((x - a_min) / L) (kami menomori dari satu), di mana a_min adalah elemen minimum dalam array A, itu dapat ditemukan dalam satu kali lintasan array asli. Satu-satunya pengecualian adalah elemen maksimum - lebih baik membuat elemen dengan nilai seperti itu dalam kelompok terpisah.
Gambar menunjukkan distribusi dari contoh yang dijelaskan di atas. Untuk kejelasan, mari lakukan ini dengan tangan kita:
Distribusi batch dilakukan dalam waktu linier dan membutuhkan memori tambahan. Harap dicatat bahwa item dari satu batch tidak dapat memberikan perbedaan maksimum antara dua item. Kami telah secara khusus memilih ukurannya dengan cara ini.
Di mana ada dua elemen yang berdekatan? Tentu saja, di batch non-kosong tetangga! Misalnya, dalam gambar, elemen dari batch ketiga dan keenam bisa berada dalam satu baris dalam array yang diurutkan, karena batch di antara mereka kosong. Jelas bahwa hanya dua elemen yang akan berdekatan - maksimum dari batch ke-3 dan minimum dari batch ke-6. Demikian pula, calon pasangan dengan selisih maksimum akan menjadi unsur maksimum kelompok pertama dan unsur minimum kelompok ketiga.
Mari kita tuliskan semua kemungkinan pasangan elemen yang dapat memberikan perbedaan terbesar. Mari kita nyatakan sebagai min (i) - elemen minimum dalam grup ke-i, sebagai max (i) - elemen maksimum.
maks (1) = -1 mnt (3) = 3
maks (3) = 4 mnt (6) = 10
maks (6) = 10 mnt (8) = 15
maks (8) = 15 mnt (10) = 20
maks (10) = 21 menit (11) = 22
Kami telah mengidentifikasi pasangan yang layak dipertimbangkan. Dalam praktiknya, Anda perlu membuat satu pass melalui semua batch, mempertahankan batch tidak-kosong terakhir dan nilai maksimum di dalamnya. Ketika kami menemukan kumpulan tidak kosong berikutnya, kami akan menemukan jumlah minimum di dalamnya dan mencoba untuk memperbarui jawabannya.
Kami akan senang - kami menyelesaikan masalah tepat waktu ...
Sebenarnya, kami menggunakan ide yang cukup terkenal dan, pada kenyataannya, mengambil langkah pertama dalam menyortir saku, dalam bahasa aslinya disebut jenis ember .
Item diatur ke dalam keranjang, dan kemudian item di setiap keranjang diurutkan.
Dalam kasus terburuk, ini berhasil , tetapi waktu berjalan rata-rata dengan jumlah batch yang memadai dan distribusi elemen yang seragam ...
“Tapi tunggu dulu, tapi bagaimana dengan kasusnya kapan , mengapa Anda tidak mempertimbangkannya? ”- pembaca yang penuh perhatian akan bertanya. Kasus ini sudah merosot, jadi kami belum mempertimbangkannya, tapi mari kita lakukan sekarang untuk kelengkapan.
Jika selisih antara minimum dan maksimum adalah nol, maka selisih maksimum juga nol. Sebenarnya itu saja.