ANALISA RUNNING TIME Maximum Contiguous Subsequence Sum I KETUT RESIKA ARTHANA NPM : 1006747864
MAGISTER ILMU KOMPUTER FAKULTAS ILMU KOMPUTER UNIVERSITAS INDONESIA
1
Deskripsi Singkat Permasalahan Maximum Contiguous Subsequence Sum (MCSS) Algorithm adalah algoritma yang digunakan untuk mencari hasil pejumlahan maksimum dari deret bilangan. Nilai maksimum dari hasil penjumlahan suatu deret akan menjadi 0 jika semua nilai dalam deret bernilai negatif. Contoh : diberikan deret bilangan : 7 -8 7 2 -1 MCSS dari deret di atas adalah 9 Contoh lain 7
-1
2
2
-9
MCSS dari deret di atas adalah 10
Deskripsi Singkat Algoritma dan Kompleksitas Ada beberapa pendekatan algoritma yang digunakan untuk menyelesaikan permasalahan Maximum Contiguous Subsequence Sum. 1. Algoritma 1 (menggunakan metode brute force) Algoritma yang pertama menggunakan metode brute force, yaitu mencoba semua jumlah sub sequence. 0 1 2 3 4 7 -1 2 2 -9 Maka akan dicari hasil jumlah dari masing-masing subsqence: jum(x,y)= dijumlahkan dari larik ke x sampai larik ke y. jum(0,0), jum(1,1), jum(2,2), jum(3,3), jum(4,4),
jum(0,1), jum(0,2), jum(0,3), jum(0,4) jum(1,2), jum(1,3), jum(1,4) jum(2,3), jum(2,4), jum(3,4)
setelah diperoleh masing-masing jumlah, maka akan dicari yang mana terbesar. Berikut adalah algoritmanya dalam bahasa pemrograman Java public {
int maxSubSum1( int [] A ) int maxSum = 0; for(int ii = 0; ii < A.length; ii++) { for( int jj = ii; jj < A.length; jj++) { int thisSum= 0; for(int kk = ii; kk <= jj; kk++) thisSum += A[kk]; if( thisSum > maxSum ) maxSum = thisSum; } } return maxSum ;
2
}
Terdapat iterasi KK sebanyak N kali yang berada dalam iterasi JJ sebanyak N kali dan berada dalam iterasi II sebanyak n kali, maka dapat dinotasikan sebagai O(N3) atau algoritma kubik. 2. Algoritma 2 (Menghilangkan 1 iterasi) Untuk mengefektifkan runtime algoritma brute force di atas, pada kasus ini dimungkinkan untuk menghilangkan 1 iterasi yang dianggap tidak efisien, sebagai gantinya nilai thisSum untuk jj bisa diisi dengan nilai thisSum sebelumnya. Berikut adalah algoritma kedua yang menghilangkan 1 iterasi. public {
int maxSubSum2( int [ ] A ) int maxSum = 0; for( int ii = 0; ii < A.length; ii++ ) { int thisSum = 0; for( int jj = ii; jj < A.length; jj++ ) { thisSum += A[jj]; if( thisSum > maxSum ) maxSum = thisSum; } } return maxSum ;
}
Dari algoritma di atas, dapat dilihat bahwa terdapat iterasi JJ sebanyak N kali dimana iterasi JJ tersebut berada dalam iterasi II sebanyak N kali juga. jadi bisa disimpulkan bahwa algoritma kedua termasuk notasi O(N2) atau algoritma kuadrat. 3. Algoritma 3 (Rekursif) Algoritma ketiga diimplementasikan dengan rekursif yang sesuai dengan pendekatan divide and conquer. Divide and Conquer adalah metode yang membagi permasalahan menjadi bagian yang lebih kecil dan kemudian menyelesaikannya. Berikut adalah algoritma dengan rekursif private int maxSumRec (int[] a, int left, int right) { int center = (left + right) / 2; if(left == right) { // Base case return a[left] > 0 ? a[left] : 0; } int int int int int int
maxLeftSum = maxSumRec (a, left, center); maxRightSum = maxSumRec (a, center+1, right); leftBorderSum=0; rightBorderSum=0; maxLeftBorderSum = 0; maxRightBorderSum=0;
for(int ii = center; ii >= left; ii--) { leftBorderSum += a[ii]; if(leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } for(int jj = center + 1; jj <= right; jj++) {
3
rightBorderSum += a[jj]; if(rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } if (maxLeftSum>maxRightSum && maxLeftSum>(maxLeftBorderSum + maxRightBorderSum)){ return maxLeftSum; }else if(maxRightSum>(maxLeftBorderSum + maxRightBorderSum)){ return maxRightSum; }else{ return (maxLeftBorderSum + maxRightBorderSum); } } public int maxSubSum3 (int [] a) { return maxSumRec (a, 0, a.length-1); }
Algoritma rekursif yang menyelesaikankan permasalahan dengan membagi dua permasalahan kemudian melakukan proses linear (menggabung atau memecah) notasi algoritma ini adalah O(N log N) 4. Algoritma 4 (Linier) Algoritma keempat menggunakan pendekatan linier. public int maxSubSum4 (int a[]) { int maxSum = 0; int thisSum = 0; for (int jj = 0; jj < a.length; jj++) { thisSum += a[jj]; if (thisSum > maxSum) { maxSum = thisSum; } else if (thisSum < 0) { thisSum = 0; } } return maxSum; }
Pada algoritma di atas, dilakukan iterasi sebanyak N kali. Pada setiap iterasi akan dicari jumlah sampa ke j. jika iterasi berikutnya memiliki jumlah lebih besar dari hasil penjumlahan sebelumnya maka hasil penjumlahan maksimum sementara akan dianggap sama dengan hasil penjumlahan pada iterasi tersebut. Namun jika hasil penjumlahan pada saat itu bernilai negatif (<0) maka hasil penjumlahan saat itu dianggap 0. Pada algoritma ini hanya menggunakan satu iterasi sebanyak N kali. Algoritma ini bisa dinyatakan dengan notasi O(N)
Metode Uji Coba Metode yang digunakan untuk uji coba analisa running time dengan mengimplementasikan algoritma ini ke dalam bahasa Java dengan editor Netbeans. Selanjutnya akan diberikan input yang sama untuk membandingkan waktu yang diperlukan masing-masing algoritma untuk mencari jumlah deret terbesar.
4
Keseluruhan algoritma ini (1-4) diimplementasikan menjadi 1 class yang diberi nama MaxSubSum.java. Disamping algoritma di atas class ini juga diisi dengan beberapa method yang menunjang proses analisa runtime. Method tersebut adalah : generateInput Method generateInput() berfungsi untuk membangkitkan array sebanyak N dengan isi masing-masing elemen dari -20 sampai 20. public int[] generateInput(int jum){ int[] arr= new int[jum]; Random ran=new Random(); for (int i=0; i<jum;i++){ arr[i]=ran.nextInt(20)-ran.nextInt(20); } System.out.println(); return arr; }
arr[i]=ran.nextInt(20)-ran.nextInt(20); berfungsi untuk menggenerate bilangan random dari - 20 sampai 20. Fungsi ran.nextInt(20) hanya menggenerate dari 0 sampai 20, jadi dibuat selisih keduanya untuk memungkinkan mendapat nilai rentang -20 sampai 20. Contoh hasil generate input (sebanyak 100) : |3|16|-14|-9|0|-7|-3|11|-14|-16|-8|5|-4|-5|15|8|13|-11|3|2|-1|11|6|0|14|-11|-1|2|0|9|-14|9|-1|3|-19|0|3|9|-9|-2|7|5|2|7|-4|-3|-4|10|1|-4|-5|-5|7|-13|2|-2|6|11|0|-9|13|14|4|7|-8|3|-4|14|-3|-12|12|0|10|-5|-3|0|-9|10|9|13|11|4|-3|-8|0|-1|-9|9|14|9|-4|-3|3|5|-5|2|6|-9|3|0|
printArray PrintArray berfungsi untuk menampilkan isi array public void printArray(int arr[]){ System.out.print("|"); for (int i=0;i<arr.length;i++){ System.out.print(""+arr[i]+"|"); } System.out.println(); }
Method main public static void main(String[] args){ MaxSubSum mss=new MaxSubSum(); int jumInput=1000; //jumlah input int[] inputArr=mss.generateInput(jumInput); mss.printArray(inputArr); //print array System.out.println("MSS 1="+mss.maxSubSum1(inputArr)); System.out.println("MSS 2="+mss.maxSubSum2(inputArr)); System.out.println("MSS 3="+mss.maxSubSum3(inputArr)); System.out.println("MSS 4="+mss.maxSubSum4(inputArr));
5
}
Jumlah input ditentukan pada main program. Pada jumlah input yang besar, beberapa algoritma terpaksa dinonaktifkan karena memiliki waktu runtime yang lama (diberi simbol NA) Netbeans dilengkapi dengan fasilitas profiling yang bisa digunakan untuk menganalisa performance dari program yang diekskusi. Fasilitas profiling ini yang digunakan penulis untuk menganalisa running time masing-masing algoritma. Cara kerja profiling program pada netbeans adalah dengan cara mencatat waktu awal dan waktu akhir sebuah method saat dijalankan. Setelah selesai method tersebut dijalankan maka akan dicari selisih waktu akhir-waktu awal untuk mendapatkan runtime masing-masing method. Langkah-langkah profiling method pada netbeans. Klik tombol profile
Pilih CPU dan tentukan part method yang ingin dicatat runtimenya
Klik Run 6
7
Analisa Running Time (dalam satuan ms) Source code terlampir (sumber dari slide kuliah dengan beberapa modifikasi) Jumlah Input 100 1000 5000 10000 100000 1000000
Algoritma 1 (ms) O(N3) 1.44 278 NA NA NA NA
Algoritma 2 (ms) O(N2) 0.191 1.89 24.8 96.0 9800 1070483
Algoritma 3 (ms) O(N log N) 1.15 6.19 25.5 47.2 536 5019
Algoritma 4 (ms) O(N) 0.009 0.038 0.17 0.364 1.22 5.91
Jumlah Data 100
Jumlah Data 1000
Jumlah Data 5000
Jumlah Data 10000
Jumlah Data 100000, maxSubSum1(NA)
Jumlah Data 1000000, maxSubSum1(NA)
Berdasarkan hasil analisa di atas, dapat disimpulkan bahwa runtime Algoritma MaxSubSum1 dengan notasi O(N3) > Algoritma MaxSubSum2 dengan notasi O(N2) > Algoritma MaxSubSum3 dengan notasi 8
O(N log N) > Algoritma MaxSubSum4 dengan notasi O(N) pada jumlah data yang besar (kira-kira di atas 10.000). Sedangkan pada jumlah data < dari 10.000 , runtime Algoritma MaxSubSum2 dengan notasi O(N2) < Algoritma MaxSubSum3 dengan notasi O(N log N)
Referensi : Algoritma diperoleh dari Slide kuliah Struktur Data & Algoritma dengan beberapa penambahan untuk diimplementasikan pada bahasa pemrograman Java
9
