Pada langkah pertama dalam desain dan analisis algoritmik, saya mengikuti buku Algorithm Design oleh Kleinberg dan Tardos. Saya menemukan Pertanyaan/Kasus yang dapat Anda temukan di halaman, solusinya memang f(n) = sqrt(n). Kekhawatiran saya adalah:

1- Mengapa saya masih menemukan log(n) lebih dapat diterima .Saya masih tidak dapat memahami nilai plus dari sqrt(n) bahkan ketika dikatakan bahwa kita akan menggunakan lebih banyak toples / percobaan .

2- dari mana kita mendapatkan sqrt(n) ?. Menggunakan k jars (percobaan) saya bisa memikirkan kenaikan n/k tapi kemudian lim n→∞ f(n) /n menuju tak terhingga adalah 1/k yang bukan 0. Saya merasa bahwa '2' di n^1 /2 berhubungan erat dengan k = 2 , jika ya bagaimana.

Terima kasih.

Kasus: Asumsikan bahwa sebuah pabrik sedang melakukan beberapa pengujian tegangan pada berbagai model stoples kaca untuk menentukan ketinggian dari mana mereka dapat dijatuhkan dan tetap tidak pecah. Pengaturan untuk percobaan ini, pada jenis toples tertentu, adalah sebagai berikut. Anda memiliki tangga dengan n anak tangga, dan Anda ingin menemukan anak tangga tertinggi dari mana Anda dapat menjatuhkan salinan toples dan tidak merusaknya. Kami menyebutnya anak tangga aman tertinggi. Mungkin wajar untuk mencoba pencarian biner: jatuhkan toples dari anak tangga tengah, lihat apakah rusak, lalu coba secara rekursif dari anak tangga n/4 atau 3n/4 tergantung pada hasilnya. Tetapi ini memiliki kelemahan bahwa Anda dapat memecahkan banyak stoples dalam menemukan jawabannya. Sebaliknya, jika tujuan utama Anda adalah menghemat stoples, Anda dapat mencoba strategi berikut. Mulailah dengan menjatuhkan toples dari anak tangga pertama, kemudian anak tangga kedua, dan seterusnya, naik satu kali lebih tinggi sampai toples pecah. Dengan cara ini, Anda hanya perlu satu toples—saat pecah, Anda memiliki jawaban yang benar—tetapi Anda mungkin harus menjatuhkannya n kali. Jadi inilah trade-off: sepertinya Anda dapat melakukan lebih sedikit tetes jika Anda ingin memecahkan lebih banyak stoples. Untuk memahami lebih baik bagaimana trade-off ini bekerja pada tingkat kuantitatif, mari kita pertimbangkan bagaimana menjalankan eksperimen ini dengan “anggaran” tetap sebesar k 1 toples. Dengan kata lain, Anda harus menentukan jawaban yang benar—anak tangga aman tertinggi—dan dapat menggunakan paling banyak k stoples untuk melakukannya. Sekarang, tolong selesaikan dua pertanyaan ini:

  1. Misalkan Anda diberi anggaran k = 2 toples. Jelaskan strategi untuk menemukan anak tangga aman tertinggi yang mengharuskan Anda menjatuhkan toples di paling f(n) kali, untuk beberapa fungsi f(n) yang tumbuh lebih lambat dari secara linier. (Dengan kata lain, seharusnya lim n→∞ f(n)/n = 0.)
1
Gin.Freecs 12 Mei 2021, 06:57

1 menjawab

Jawaban Terbaik

log(n) adalah waktu terbaik, tetapi membutuhkan log(n) toples.

Jika kita dibatasi oleh 2 toples, kita bisa menerapkan sqrt-strategy.

Jatuhkan toples pertama dari beberapa ketinggian, membentuk urutan dengan perbedaan meningkat.

Untuk selisih 1,2,3,4... kita memiliki barisan tinggi 1,3,6,10,15,21... (disebut bilangan segitiga). Saat toples pertama pecah, kita mulai dari previous height+1, dengan langkah 1, sampai yang kedua pecah.

Jika toples pertama pecah pada usia 15, kami menjatuhkan toples kedua menggunakan 11, 12, 13, 14 .

Strategi tersebut memberikan O(sqrt(n)) penurunan, karena rumus bilangan segitiga adalah n~T(k)=k*(k+1)/2, jadi untuk mencapai ketinggian di atas n, kita harus menggunakan sekitar k ~= sqrt(n) percobaan, dan kurang dari k uji coba untuk toples kedua.

2
MBo 12 Mei 2021, 06:08