images

String Matching Algorithm

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(nm + 1) = O(mn).

Misalnya:

Teks:    aaaaaaaaaaaaaaaaaaaaaaaaaaaaab

Pattern: aaaab

Guys… untuk Kompleksitas Waktu Kasus Rata-ratanya di hitung sendiri yah….  :)

 

Share

Leave a Reply

Your email address will not be published. Required fields are marked *