Penerapan Teknik Dekomposisi Square Root dan Algoritma Mo's pada Rancangan Algoritma Studi Kasus: SPOJ Klasik Counting Diff-Pairs - Abdul Majid Hasani; Rully Soelaiman; Fajar Baskoro (Direktorat Riset dan Pengabdian Masyarakat (DRPM), ITS, 2018)
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.