Guys.. Lama sudah saya tidak nge-publish yang model-model seperti ini, biasanya hanya bercerita saja dan akhirnya hari ini putuskan untuk menulisnya sebagai penutup postingan dibulan maret ini, String Matching Algorithm algoritma ini sering sekali dikenal dengan Algoritma Pencarian String, mengingat materi sewaktu dibangku perkuliahan, pada mata kuliah Rancangan Analisis Algoritma (RAA) sedikit di bahas tentang algoritma tersebut.
Ketika membahas String Matching Algorithm pasti tidak akan ketinggalan dengan bahasan tentang teks dan pattern karena kedua bahasan tersebut saling berkaitan pada algoritma itu. Teks atau text yaitu string yang panjangnya sebanyak n karakter sedangkan pattern yaitu string dengan panjang m karakter dimana m < n yang akan dicari di dalam teks. Selain dua hal itu ada juga yang disebut dengan Locate yaitu lokasi pertama di dalam teks yang bersesuaian dengan pattern.
String Matching Algorithm merupakan algoritma pencarian yang alurnya sangat mudah dipahami jika dibandingkan dengan algoritma pencarian dalam teks lainnya , untuk lebih memahami langsung menyimak contoh ini.
Contoh1:
Teks : Siapa yang menjemput Papa dari kota Balikpapan?
Pattern : apa
Jadi pada teks “Siapa yang menjemput Papa dari kota Balikpapan?” terdapat tiga kata apa yang ditemukan
Contoh 2:
Teks : nobody noticed him
Pattern : not
cara mencarinya untuk lebih detailnya sbb:
nobody noticed him
s=0 not
s=1 not
s=2 not
s=3 not
s=4 not
s=5 not
s=6 not
s=7 not
jadi kata not dalam teks “nobody noticed him” ditemukan pada karakter ke-8.
Kompleksitas algoritma
Ketika membahas tentang algoritma dalam Analisis Algoritma pasti akan berhubungan dengan kompleksitas dimana kompleksitas itu merupakan besaran yang dipakai untuk menerangkan model abstrak pengukuran. Pada kompeksitas algoritma terdapat dua kompleksitas yaitu kompleksitas Waktu dan kompleksitas Ruang.
Kompleksitas waktu, T(n), diukur dari jumlah tahapan komputasi yang dibutuhkan untuk menjalankan algoritma sebagai fungsi dari ukuran masukan n.
Kompleksitas ruang, S(n), diukur dari memori yang digunakan oleh struktur data yang terdapat di dalam algoritma sebagai fungsi dari ukuran masukan n.
Nah… untuk kompleksitas waktu (T(n)) masih dibagi lagi menjadi 3 bagian, yaitu:
- Tmax(n) : kompleksitas waktu untuk kasus terburuk (worst case), –>kebutuhan waktu maksimum.
- Tmin(n) : kompleksitas waktu untuk kasus terbaik (best case), –>kebutuhan waktu minimum.
- Tavg(n) : kompleksitas waktu untuk kasus rata-rata (average case) –>kebutuhan waktu secara rata-rata
Dan dalam tiap algoritma mempunyai perhitungan sendiri-sendiri untuk menentukan kompleksitasnya tapi biasanya perhitungan kompleksitas itu ditentukan dari setiap operasi pada pseudocode suatu algoritma.
Pada String Matching Algorithm dapat ditentukan Kompleksitas waktu kasus terbaik adalah O(n).
Kasus terbaik terjadi jika karakter pertama pada pattern P tidak pernah sama dengan karakter teks T yang dicocokkan. Pada kasus ini, jumlah perbandingan yang dilakukan paling banyak n kali misalnya:
Teks : String ini berakhir dengan zz
Pattern : zz
Sedangkan untuk Kompleksitas waktu Kasus terburuk: m(n – m + 1) = O(mn).
Misalnya:
Teks: aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
Pattern: aaaab
Guys… untuk Kompleksitas Waktu Kasus Rata-ratanya di hitung sendiri yah…. 🙂
