Algoritma pencarian: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
k Bot: Perubahan kosmetika |
||
Baris 7:
=== Pencarian List ===
Algoritma pencarian list mungkin adalah algoritma pencarian paling dasar. Tujuannya adalah mencari sebuah elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi yang terkait dengan kunci). Oleh karena hal ini adalah masalah yang lazim dalam [[ilmu komputer]], [[kompleksitas komputasi]] algoritma-algoritma tersebuh telah dipelajri dengan baik. Algoritma paling sederhana adalah [[pencarian linear]], yang secara sederhana melihat setiap elemen dari list secara berurutan. [[Waktu pengerjaan]] algoritma ini adalah [[notasi O besar|O]](''n''), dimana ''n'' adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. Algoritma pencarian list yang lebih canggih adalah [[pencarian biner]]; waktu pengerjaannya adalah [[notasi O besar|O]](log ''n''). Waktu pengerjaannya jauh lebih baik daripada [[pencarian linear]] untuk list yang memiliki data banyak, tetapi sebelum dilakukan pencarian list terlebih dahulu harus terurut (lihat [[algoritma pengurutan]]) dan juga harus dapat diakses secara acak ([[pengaksesan acak]]). [[Pencarian interpolasi]] adalah lebih baik dari pencarian biner untuk list terurut yang sangat besar dan terdistribusi merata. [[Algoritma Grover]] adalah sebuah [[komputer kuantum|algoritma kuantum]] yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut.
[[Tabel hash]] juga digunakan untuk pencarian list, hanya memerlukan waktu yang konstan untuk mencari pada kasus rata-rata, tetapi memiliki ''overhead'' ruang yang lebih dan pada kasus terburuk waktu pengerjaannya adalah O(''n''). Pencarian lain yang berdasarkan struktur data khusus, menggunakan pohon pencarian biner yang ''self-balancing'' ([[self-balancing binary search tree]]) dan membutuhkan waktu pencarian O(log ''n''); hal ini dapat dipandang sebagai pengembangan dari ide utama pencarian biner untuk memungkinkan penyisipan dan penghapusan yang cepat. Lihat [[array asosiatif]] untuk diskusi lanjut dari struktur data pencarian list.
Baris 28:
== Pemenuhan Kendala ==
Ini adalah satu jenis pencarian yang memecahkan [[permasalahan pemenuhan kendala]] dimana, bukan dengan melihat sebuah jalur, solusinya adalah sebuah himpunan nilai yang diberikan pada sebuah himpunan peubah. Karena peubah-peubah dapat diproses dengan urutan apa saja, algoritma pencarian pohon biasa adalah tidak efisien. Metode pemecahan permasalahan kendala memuat [[pencarian kombinatorial]] dan [[lacak balik]], keduanya mengambil keuntungan dari kebebasan yang diasosiasikan dengan permasalahan kendala.
== Pencarian Interpolasi ==
Bayangkan perihal mencari sebuah kata dalam sebuah kamus. Diberikan sembarang kata, anda memiliki beberapa ide perihal dimana membuka kamus untuk mendapatkan huruf pertama dari kata. Dari sana, anda akan memiliki ide untuk membuka beberapa halaman lagi untuk mendapatkan kota yang hampir mirip denan kata. Dan seterusnya, ini adalah ide dasar dari [[pencarian interpolasi]].
== Jenis Lain ==
| |||