ANALISIS EDIT DISTANCE MENGGUNAKAN ALGORITMA DYNAMIC PROGRAMMING

Abstract

Edit distance merupakan jumlah minimum point mutation yang diperlukan untuk merubah suatu string ke string yang lain. Point mutation tersebut adalah mengganti, menambah dan menghapus
sebuah karakter. Konsep edit distance banyak digunakan dalam proses manipulasi data berbagai aplikasi komputer. Berbagai algoritma dapat digunakan dalam pencarian dan penentuan edit distance.
Dalam penelitian ini, dilakukan eksperimen untuk mencari edit distance menggunakan algoritma dynamic programming. Sedangkan proses perhitungannya dibantu dengan fungsi-fungsi yang ada dalam Microsoft Excel. Hasil eksperimen menunjukkan kompleksitas waktu (time complexity) untuk
algoritma dynamic programming adalah O(|s1|*|s2|). Jika s1 dan s2 mempunyai panjang yang hampir sama, katakanlah n, maka kompleksitas waktunya adalah O(n2). Kompleksitas ruang (spacecomplexity) untuk algoritma ini juga O(n
2), karena keseluruhan dari matriks digunakan untuk menemukan solusi yang optimal.
Kata kunci : edit distance, dynamic programming, kompleksitas.