| [Pelawat (112.0.*.*)]jawapan [Cina ] | Masa :2023-10-29 | Terdapat 10,000 keping data yang disusun dari kecil hingga besar, dan kesimpulannya dapat dicapai dengan mencari sehingga 14 kali dengan kaedah carian binari. Formula untuk kaedah carian binari ialah alog2(n)b. A, B dan N ialah semua integer positif.
Kerana 2^9=512 tidak mencukupi untuk mendapatkan semula 1000, maka sekali lagi: 2^10=1024 sudah cukup untuk mendapatkan semula 1000. Bilangan carian bipartit adalah berdasarkan 2, dan kuasa ke-10 2 adalah 1024, yang boleh didapati sepenuhnya, jadi ia hanya perlu 10 kali paling banyak.
Untuk carian binari untuk tatasusunan yang diperintahkan dengan unsur n, bilangan perbandingan yang akan dianalisis boleh dianalisis dengan melukis pokok keputusan binari.
log2n)。 Apabila n besar, perbezaan kecekapan antara keduanya sangat besar. Sebagai contoh, jika terdapat satu juta entri dalam jadual, anda perlu mencari ID tertentu di dalamnya. Jika anda mencari secara berurutan, anda perlu mencari purata 500,000 keping data. Dengan dikotomi, ia boleh didapati tidak lebih daripada 20 kali.
Bilangan carian kes terburuk dibundarkan kepada keseluruhan terdekat (log2(n 1)). Dalam kes yang paling teruk, carian tidak selesai sehingga elemen tunggal terakhir, kerana setiap carian dikurangkan separuh, jadi jumlah keseluruhan carian (log2 (n 1)) diperlukan. |
|
