| [Pengunjung (112.0.*.*)]jawaban [Cina ] | Waktu :2023-10-29 | Ada 10.000 keping data yang diurutkan dari kecil hingga besar, dan kesimpulannya dapat dicapai dengan mencari hingga 14 kali dengan metode pencarian biner. Rumus untuk metode pencarian biner adalah alog2(n)b. a, b, dan n semuanya adalah bilangan bulat positif.
Karena 2^9=512 tidak cukup untuk mengambil 1000, sekali lagi: 2^10=1024 sudah cukup untuk mengambil 1000. Jumlah pencarian bipartit didasarkan pada 2, dan pangkat 10 dari 2 adalah 1024, yang dapat ditemukan sepenuhnya, sehingga hanya perlu paling banyak 10 kali.
Untuk pencarian biner untuk array terurut dengan n elemen, jumlah perbandingan yang akan dianalisis dapat dianalisis dengan menggambar pohon keputusan biner.
log2n)。 Ketika n besar, perbedaan efisiensi antara keduanya sangat besar. Misalnya, jika ada satu juta entri dalam satu tabel, Anda perlu menemukan ID tertentu di dalamnya. Jika Anda mencari secara berurutan, Anda perlu menemukan rata-rata 500.000 keping data. Dengan dikotomi, dapat ditemukan tidak lebih dari 20 kali.
Jumlah pencarian kasus terburuk dibulatkan ke atas ke seluruh terdekat (log2(n 1)). Dalam kasus terburuk, pencarian tidak selesai sampai elemen tunggal terakhir, karena setiap pencarian dibelah dua, sehingga seluruh jumlah pencarian (log2 (n 1)) diperlukan. |
|
