Make Divide and Conquer buat nyelesein problem Fibonacci

Tiba tiba saya kepikiran soal algoritme yang dulu dipelajari di kampus. Algoritme kan pada dasarnya merupakan langkah terstruktur buat menyelesaikan masalah tertentu. Jadi belom tentu suatu algoritme yang cocok buat problem A bisa diterapkan dengan tepat di problem B. Salah satu algoritme yang pernah ditanyain waktu saya interview kerja (di tempat yang saya ga jadi ambil) adalah algoritme divide and conquer dan dynamic programming.Saya pernah belajar dua algoritme ini tapi saya ngga pernah ngerti kapan saya harus memutuskan pake divide and conquer atau dynamic programming. Hingga beberapa menit yang lalu saya mendapat sedikit pencerahan (makanya langsung ditulis biar ga lupa).

Oke kita coba liat dulu deh divide and conquer (saya inget kalo yang ini ni) yang dulu pernah diterapkan oleh bangsa Belanda yang sukses megobrak-abrik Nusantara. Algoritme ini udah ada sejak awal abad ke 19. Bahkan penerapannya sebenernya udah dari kapan tau, tapi baru dirumuskan aja kayaknya. Pada dasarnya algoritme ini bekerja dengan cara memecah suatu masalah besar menjadi sub-sub masalah hingga ke sub masalah terkecil dan menyelesaikan setiap sub masalah tersebut. Istilah peribahasanya, sedikit-sedikit lama lama jadi bukit. Ya secara logika kan kalo ada masalah besar kita selesein pelan-pelan dari yang paling gampang dulu, satu per satu, lama-lama kan selesai tuh semua masalah.

Nah, misalnya kita diberikan masalah Fibonacci. Problem yang selalu diberikan di hamper semua mata kuliah. Kan Fibonacci itu intinya jumlah dua bilangan sebelumnya dalam suatu deret, atau yang kalo ditulis dalam bahasa matematika jadi begini:

Mari kita coba pecahkan problem ini dengan algoritme divide and conquer. Problem ini bisa kita selesaikan dengan algoritme yang kira-kira bunyinya begini:

If n<=1 return n

else return F(n-1) + F(n-2)

Oke, kalo algoritme itu kita jalanin untuk meghitung Fib(4), yang terjadi adalah seperti tree dibawah ini:

Coba deh liat, Fib(2) diulang perhitungannya sampe 2 kali.. Bayangkan kalo kita menghitung Fib(6), maka akan nada penghitungan F(6)=F(5) + F(4), F(5)=F(4)+F(3), yang melibatkan dua kali penghitungan F(4) yang artinya aka nada 4 kali penghitungan F(2). Berarti kalo kita mau itung F(n) bakal makin banyak perulangan yang dilakukan dan bakalan menuju ke eksponensial time ni algoritmenya.

Hmm, gimana cara menyelesaikan si Fibonacci ini supaya jalannya algoritme ga panjang ya? Kayaknya sih bisa pake Dynamic Programming.. Oke, nanti saya cobain lagi deh.. hehe..