Heru C Rustamaji

Pak dosen juga nge-Blog

Divide and Conquer

Salah satu strategi penyelesaian masalah dalam bidang komputasi adalah menggunakan divide dan conquer. Caranya adalah memecah problem menjadi beberapa sub problem. Masing masing sub problem tersebut dipecahkan dan selanjutnya solusinya digabungkan dengan suatu mekanisme tertentu. Apabila sub problem tersebut masih tidak bisa dipecahkan secara langsung, maka sub problem tersebut dipecah kembali menjadi beberapa sub problem secara divide an conquer. Dalam aplikasinya, hal tersebut bisa diselesaikan secara rekursif.

BINARY SEARCH

Salah satu penggunaan strategi penyelesaian menggunakan divide and conquer adalah dalam algoritma searching menggunakan binary search untuk suatu array yang telah terurut. Dengan menggunakan algoritma ini maka kompleksitas algoritma ini adalah O(log n). inilah algoritmanya :

int BinSearch (KeyType A [], int n, KeyType Key,int & Where)
// Search A [0 .. n-1] for Key. If found return
// TRUE and set Where to the subscript where found;
// otherwise, return FALSE . Assume A is in ascending
// sorted order and n > 0 .
{
int Lo = 0, Hi = n;
assert (n > 0);
while (Lo < Hi - 1)
{
Where = (Lo + Hi) / 2;
if (Key < A [Where])
Hi = Where;
else
Lo = Where;
}
Where = Lo;
return (Key == A [Lo]);
}

MERGE SORT

Inilah salah satu alternatif melakukan pengurutan /sorting menggunakan strategi divide and conquer. Kompleksitasnya algoritmanya dinyatakan dengan relasi rekurens T (n) = 2T (n/2) + n yang akan menghasilkan solusi O(n lg n)

MergeSort (TYPE A [], int n)
{
if (n > 1)
{
MergeSort (A, n/2);
MergeSort (A + n/2, n - n/2)
Merge (A, n/2, A + n/2, n - n/2, A)
}
}

Kelemahan merge sort ini adalah dibutuhkan memory ekstra pada saat fase Merge, bukan menggunakan teknik ‘in-place’.

PERKALIAN MATRIKS

Perkalian matriks yang biasa dilakukan, apabila dibuat prosedurnya secara biasa akan menghasilkan kompleksitas O(n^3). Hal tersebut dilakukan dengan menghitung masing masing elemen hasil perkalian matriks dengan rumus

C(i,j) = ∑ A(i,k) B(k,j)

Namun hal tersebut bisa dipangkas lagi menggunakan algoritma strassen, dimana setiap matriks dibagi menjadi 4 partisi, sebagai contoh sebuah matriks A dipartisi menjadi

A11 | A12
—————–
A21 | A22

dan dilakukan perhitungan sebagai berikut

M1 = (A11 + A22)(B11 + B22)

M2 = (A11 + A22)B11

M3 = A11(B11 − B22)

M4 = A22(B21 − B11)

M5 = (A11 + A12)B22

M6 = (A21 − A11)(B11 + B12)

M7 = (A12 − A22)(B21 + B22)

Diperoleh hasil perkalian matriks sebagai berikut:

C11 = M1 + M4 − M5 + M7

C12 = M3 + M5

C21 = M2 + M4

C22 = M1 + M3 − M2 + M6

Kompleksitas algoritmanya dapat dihitung dengan formulasi berikut

M (n) = 7M (n/2)

M (1) = 1;

Relasi rekurens tersebut akan menghasilkan solusi O(n ^ 2.807)

Iklan

Mei 17, 2008 - Posted by | IT |

1 Komentar »

  1. kalo komputernya ngehang bagaimana pak?
    jadi divide terus tapi ndak bisa bisa conquer?

    Komentar oleh konco lawas | Juni 11, 2008 | Balas


Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: