Penerapan Teknik Dekomposisi Square Root dan Algoritma Mo's pada Rancangan Algoritma Studi Kasus: SPOJ Klasik Counting Diff-Pairs

Abstract

Diberikan sebuah sekuen bilangan A dengan jumlah N , M baris kueri, dan selisih mutlak bernilai k. Terdapat  operasi kueri untuk mencari jumlah pasangan angka dalam jarak tertentu di sekuen bilangan A yang memiliki selisih mutlak sama dengan atau lebih dari k.Pada penelitian ini akan dirancang penyelesaian masalah  yang disampaikan pada paragraf pertama dengan menggunakan algoritma Square Root Decomposition, Mo’s Algorithm, danstruktur   data   Fenwick   Tree.  √Solusi   yang   didesain   memiliki kompleksitas waktu O((N +M ) N K log mv), dimana N adalahjumlah  elemen  pada  b√aris  sekuen  yang  diberikan,  M  adalahjumlah operasi kueri, N  adalah  konstanta,  K  adalah jumlah langkah peyelesaian, dan log mv adalah kompleksitas Fenwick Tree.Algoritma yang didesain dapat menyelesaikan permasalahan yang diberikan dengan benar. Waktu eksekusi program yang mengimplementasi algoritma yang dirancang tidak melebihi batas waktu eksekusi program yang telah diberikan, yaitu 1.78 detik. Sehingga dapat disimpulkan algoritma yang didesain dapat menyelesaikan permasalahan yang diberikan.