My first Magazine pemrograman-kompetitif-dasar | Page 51

4.3 Optimisasi Teknik Brute Force
Algoritma 19 Solusi permasalahan Mengatur Persamaan.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
function COUNT T RIPLETS ()
count ← 0
for i ← 1, N do
for j ← 1, N do
for k ← 1, N do
p ← a[i]
q ← a[ j]
r ← a[k]
if (p + q + r) = 0 then
count ← count + 1
end if
end for
end for
end for
return count
end function
Apakah ada solusi yang lebih baik? Sebenarnya, kita bisa mengambil suatu observasi
sederhana yang cukup berguna untuk mempercepat solusi kita.
Observasi: Jika kita sudah menentukan nilai p dan q, maka nilai r haruslah −(p + q).
Berdasarkan observasi tersebut, kita dapat mencoba semua kemungkinan p dan q, lalu
memeriksa apakah −(p + q) terdapat di dalam array. Untuk mempercepat, pencarian −(p + q)
bisa menggunakan binary search . Implementasi solusi tersebut terdapat pada Algoritma 20.
Algoritma 20 Solusi permasalahan Mengatur Persamaan yang dioptimasi.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
function COUNT T RIPLETS F AST ()
count ← 0
for i ← 1, N do
for j ← 1, N do
p ← a[i]
q ← a[ j]
r ← −(p + q)
if EXIST (r) then
count ← count + 1
end if
end for
end for
return count
end function
Pada Algoritma 20, fungsi EXIST (r) adalah fungsi untuk memeriksa keberadaan r di himpunan
{a 1 , a 2 , ..., a N } dengan menggunakan binary search (tentunya setelah diurutkan). Kompleksitas
dari COUNT T RIPLETS F AST sendiri adalah O(N 2 log N).
Kompleksitas O(N 2 log N) sudah cukup untuk N yang mencapai 2.000. Dari sini kita belajar
bahwa optimisasi pada pencarian kadang diperlukan, meskipun ide dasarnya adalah brute force .
41