Searching: Struktur Data

SEARCHING PADA STRUKTUR DATA

Searching - Sistem komputer yang sering digunakan untuk menyimpan data dalam jumlah besar dari yang catatan individu harus diambil menurut beberapa kriteria pencarian. Sehingga penyimpanan data yang efisien untuk memudahkan pencarian cepat merupakan isu penting. Pada bagian ini, kita akan menyelidiki kinerja beberapa algoritma pencarian dan struktur data yang akan di gunakan.

Searching Sequential

Mari kita memeriksa berapa lama waktu yang dibutuhkan untuk menemukan item yang cocok dengan kunci dalam koleksi yang telah kita bahas sejauh ini. Ada 3 macam waktu di bawah ini :

1.  waktu rata-rata
2.  waktu terburuk dan
3.  waktu terbaik mungkin.

Namun, kita umumnya akan sangat peduli dengan waktu terburuk sebagai perhitungan berdasarkan kali terburuk dapat menyebabkan dijamin prediksi kinerja. Nyaman, waktu terburuk umumnya lebih mudah untuk menghitung dari kali rata-rata.

Jika ada n item dalam koleksi kami - apakah itu disimpan sebagai array atau linked list - maka jelas bahwa dalam kasus terburuk, ketika tidak ada item dalam koleksi dengan kunci yang diinginkan, maka n perbandingan dari kunci dengan kunci-kunci item dalam koleksi akan harus dibuat.
(baca juga: Konsep tree dalam struktur data)

Untuk mempermudah analisis dan perbandingan algoritma, kita mencari sebuah operasi dominan dan menghitung berapa kali operasi dominan harus dilakukan. Dalam kasus pencarian, operasi dominan adalah perbandingan, karena pencarian memerlukan perbandingan n dalam kasus terburuk, kita mengatakan ini adalah O (n) (mengucapkan ini "big-Oh-n" atau "Oh-n") algoritma. Kasus terbaik - di mana perbandingan pertama mengembalikan pertandingan - memerlukan perbandingan tunggal dan O (1). Rata-rata waktu tergantung pada probabilitas bahwa kunci akan ditemukan dalam koleksi - ini adalah sesuatu yang kita tidak akan mengharapkan untuk mengetahui di sebagian besar kasus. Jadi dalam hal ini, seperti dalam kebanyakan orang lain, estimasi waktu rata-rata adalah sedikit utilitas. Jika kinerja sistem sangat penting, yaitu itu bagian dari sistem kritis kehidupan, maka kita harus menggunakan kasus terburuk dalam perhitungan desain kami karena mewakili kinerja dijamin terbaik.
Dalam menyelesaikan semua tugas input dan juga output itu disebut dengan Real Time System.

Binary Search

Namun, jika kita menempatkan atau menyimpan barang-barang dalam sebuah array dan mengurutkan mereka baik menaik atau menurun pada tombol pertama, maka kita dapat memperoleh kinerja yang lebih baik dengan sebuah algoritma yang disebut pencarian biner.

Binary Searching

Dalam pencarian biner, pertama kita membandingkan kunci dengan item di posisi tengah dari array. Jika ada pertandingan, kita dapat kembali segera. Jika kuncinya adalah kurang dari tombol tengah, maka item dicari harus terletak di bagian bawah dari array; jika itu lebih besar maka item dicari harus terletak di bagian atas dari array. Jadi kita ulangi prosedur di bawah (atau atas) setengah dari array. Dalam Array juga ada fungsi dari Record.
(Baca juga: contoh program array)

Nah, begitulah pembahasan tentang searching pada struktur data. Selanjutnya Anda boleh melanjutkan ke pembahasan dari SORTING. Terima kasih semoga bermanfaat !

Tweet

Subscribe to receive free email updates: