My first Magazine pemrograman-kompetitif-dasar | Page 65

5.4 Studi Kasus 3: Mencari Nilai Terbesar
Pertama kita definisikan tahap-tahapnya:
• Divide : jika array berukuran besar (lebih dari satu elemen), bagi menjadi dua subarray .
Kemudian, lakukan pencarian secara rekursif pada masing-masing subarray tersebut.
• Conquer : ketika array hanya berisi satu elemen, nilai terbesarnya pasti adalah elemen
tersebut.
• Combine : nilai terbesar dari array adalah maksimum dari nilai terbesar di subarray pertama
dan nilai terbesar di subarray kedua.
Implementasi Pencarian Nilai Terbesar
Ide pencarian nilai terbesar secara divide and conquer terdapat di Algoritma 25.
Algoritma 25 Pencarian nilai terbesar secara divide and conquer .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
function FIND M AX (arr, le f t, right)
if le f t = right then
return arr[le f t]
else
mid ← (le f t + right) div 2
le f tMax ← FIND M AX (arr, le f t, mid)
rightMax ← FIND M AX (arr, mid + 1, right)
return max(le f tMax, rightMax)
end if
end function
Analisis Algoritma Mencari Nilai Terbesar
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1) O(1)
Gambar 5.34: Pembagian dan kompleksitas untuk menyelesaikan tiap subarray .
Setiap operasi divide, conquer, dan combine bekerja dalam O(1). Pada tiap kedalaman,
kompleksitas yang dibutuhkan adalah sebanyak subarray pada kedalaman tersebut. Kedalaman
ke-i (dimulai dari 1) memiliki banyak subarray sebanyak 2 i−1 . Sehingga kedalaman ke-1 memiliki
2 0 = 1 subarray , kedalaman ke-2 memiliki 2 1 = 2 subarray , kedalaman ke-3 memiliki 2 2 = 4
subarray , dan seterusnya.
Maka operasi conquer dilaksanakan sebanyak 1 + 2 + 4 + 8 + ... + 2 L kali, dengan L adalah
banyak kedalaman rekursif dari pembagian array , yaitu L = log N. Dengan 2 L ≈ N, keseluruhan
total operasi adalah 1 + 2 + 4 + 8 + ... + 2 L = 2 L+1 − 1 = 2N operasi. Kompleksitas akhirnya menjadi
O(N).
Ternyata, strategi ini tidak lebih baik dari mencari nilai maksimum satu per satu menggunakan
perulangan. Kesimpulannya, divide and conquer tidak selalu dapat mengurangi kompleksitas
solusi naif.
55