Pencarian linear: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
|||
Baris 2:
Algoritma ini beroperasi dengan memeriksa setiap elemen dari sebuah list sampai sebuah kecocokan ditemukan. Pencarian linear bekerja dalam [[notasi O besar|O]](n). Jika data terdistribusi secara acak, rata-rata ada n/2 pembandingan akan dilakukan. Kasus terbaik adalah ketika nilai yang dicari adalah elemen pertama dari list, kasus ini hanya memerlukan 1 pembandingan. Kasus terburuk adalah ketika nilai yang dicari tidak ada dalam list, yang memerlukan n pembadingan.
Modul List pada pustaka standard [[OCaml]] mendefinisikan sebuah fungsi "mem" yang mengembalikan nilai true jika elemen yang diberikan berada dalam list atau false jika tidak. Fungsi ini dinyatakan sebagai berikut:
<pre>
let rec mem x = function
[] -> false
| h :: t -> h=x || mem x t
</pre>
Pencarian linear dapat diimplementasikan secara matematika dengan pencocokan pola :
<pre>
Mem[x_, {___, x_, ___}] := True
Mem[_, _] := False
</pre>
Pencarian linear dapat digunakan untuk mencari sebuah list tak berurut. [[Pencarian biner]] adalah pencarian yang lebih efisien yang dapat digunakan untuk mencari sebuah list berurut.
Jika diperlukan beberapa kali pencarian, disarankan untuk menggunakan [[struktur data]] yang lebih efisien. Satu pendekatan adalah dengan mengurutkan terlebih dahulu kemudian gunakan pencarian biner untuk setiap pencarian. Cara lain yang lazim adalah membuat sebuah [[tabel hash]] dan dilakukan pencariaan hash.
==Acuan==
* [[Donald Knuth|Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.1: Sequential Searching, pp.396–408.
[[Kategori:Ilmu komputer]]
[[Kategori:Algoritma]]
[[Kategori:Algoritma Pencarian]]
[[de:Lineare Suche]]
[[it:Ricerca sequenziale]]
[[nl:Lineair zoeken]]
[[pt:Busca linear]]
[[fi:Lineaarihaku]]
| |||