Penerapan Teknik Dekomposisi Square Root dan Algoritma Mo's pada Rancangan Algoritma Studi Kasus: SPOJ Klasik Counting Diff-Pairs
| Main Authors: | Hasani, Abdul Majid; Departemen Informatika Institut Teknologi Sepuluh Nopember, Soelaiman, Rully; Departemen Informatika Institut Teknologi Sepuluh Nopember, Baskoro, Fajar; Departemen Informatika Institut Teknologi Sepuluh Nopember |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
Lembaga Penelitian dan Pengabdian Kepada Masyarakat (LPPM), ITS
, 2018
|
| Subjects: | |
| Online Access: |
http://ejurnal.its.ac.id/index.php/teknik/article/view/29603 http://ejurnal.its.ac.id/index.php/teknik/article/view/29603/4879 http://ejurnal.its.ac.id/index.php/teknik/article/downloadSuppFile/29603/3204 http://ejurnal.its.ac.id/index.php/teknik/article/downloadSuppFile/29603/3206 |
Daftar Isi:
- 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.