بسم الله الرحمن الرحيم
Di posting sebelumnya telah dibahas identitas penting dari barisan Fibonacci, yaitu relasi rekurens yang biasa dikenal
\[F_{n}=F_{n-1}+F_{n-2}\]
Kita akan membahas lebih lanjut relasi ini dan menentukan cara untuk menghitung barisan Fibonacci ini.
Bagi yang belum tahu tentang Fibonacci silahkan lihat post sebelumnya: About Fibonacci : Menghitung Kelinci - part 1
Relasi Rekurens
Sekilas relasi rekurens intinya adalah menggunakan fungsi yang sama dalam pemanggilan fungsi, seperti \(L_{n}=L_{n-1}+2n-1\). Terlihat bahwa di dalam fungsi \(L_{n}\) ada fungsi \(L_{n-1}\). Dengan kata lain nilai fungsi parameter N bergantung pada fungsi yang sama dengan parameter N-1. Dan juga relasi rekursif berguna mengubah problem yang besar menjadi problem yang lebih kecil. Fibonacci ke-N menjadi Fibonacci ke-(N-1) dan ke-(N-2). Kurang lebih seperti itu cara kerja fungsi rekursif.
Dalam pendefinisian fungsi rekursif ada 2 hal yang harus diperhatikan : basis dan rekurens.
Dengan memanfaatkan definisi rekursif ini kita bisa implementasikan Fibonacci ke-N dengan fungsi rekursif seperti berikut.
Tapi ada kelemahan dalam pemanggilan fungsi seperti ini. Coba perhatikan skema pemanggilan fungsi di bawah!
Inti dari DP adalah mengubah parameter menjadi state fungsi dan menyimpan setiap state yang dilalui fungsi dalam suatu struktur data. Sehingga sekali kita telah menghitungnya kita tidak perlu mengulanginya lagi.
Dalam membuat konstruksi DP kita dapat memakai 2 cara : top-down dan bottom-up.
1. DP Top-Down
Style yang satu ini cukup mudah. Dengan menggunakan fungsi rekursif yang sebelumnya dan sedikit modifikasi maka akan terbentuk DP top-down.
Jika kita lihat, kelemahan rekursi yang sebelumnya hanyalah pada kurangnya penyimpanan state sehingga menyebabkan overlap. Maka sekarang kita akan menyimpan nilai semua state F(n) pada suatu variabel (misal array) yang kita namakan variabel memo sehingga kita tidak perlu menghitung berulang-ulang. Metode ini disebut memoization/memoisasi.
Coba perhatikan ilustrasi di bawah!
Dengan menyimpan nilai state nilai F(3) bisa dimanfaatkan langsung tanpa menghitung lagi dari F(2) dan F(1). Kurang lebih implementasinya DP top-down seperti berikut.
2. DP Bottom-Up
Jika DP top-down membuat solusi dengan fungsi rekursif (yang cenderung mengecil ke basis), maka DP bottom-up membuat solusi dari basis lalu membesar ke state berikutnya sampai batas yang diinginkan. Bisa dikatakan style ini kebalikan dari style sebelumnya.
Coba perhatikan ilustrasi berikut!
Dari gambar terlihat bahwa relasi rekursif F(n) = F(n-1) + F(n-2) digunakan untuk membangun solusi F(3), F(4), dan seterusnya hingga F(8). Dimulai dari basis F(1) dan F(2), solusi ini membangun solusi hingga F(n) yang diinginkan.
Implementasinya cukup dengan iterasi biasa untuk mengisi F(3) sampai F(n) sehingga masih cukup mudah dibuat. Dan karena implementasinya bebas rekursi maka untuk Fibonacci dengan urutan yang sangat besar (contoh: F(2000,000,000)) tidak akan mengalami stack overflow ketika pemanggilannya seperti terjadi pada fungsi rekursi. Inilah keunggulan utama DP bottom-up dibanding top-down. Meskipun kadang implementasi bottom-up umumnya lebih susah dari top-down karena dimulai dari basis dan pemilihan rekurens yang harus ekstra hati-hati (karena bisa jadi tidak semua parameter memo digunakan dalam DP). Pengalaman saya sendiri saat ICPC kemarin tim saya harus bergelut selama hampir sejam untuk mendebug solusi DP bottom-up karena ada bagian yang harusnya tidak dimasukkan rekurens ternyata belum dikecualikan.
Kurang lebih implementasinya seperti berikut.
Dan perlu diketahui untuk kedua solusi DP di atas memiliki kompleksitas \(O(N)\), yaitu linear terhadap nilai N. Sehingga untuk N < 100 juta, runtime yang dibutuhkan masih sekitar 1 detik atau kurang.
Untuk N yang sangat besar kita tidak dapat memakai solusi ini karena pasti akan mendapat verdict TLE karena runtime yang dibutuhkan bisa 100 detik atau malah jauh lebih besar. Maka ada cara yang lebih baik menggunakan teknik Divide and Conquer dengan perkalian matriks.
Tunggu di post berikutnya :
About Fibonacci : Divide and Conquer Approach; Matrix Exponentiation- part 3
Dalam pendefinisian fungsi rekursif ada 2 hal yang harus diperhatikan : basis dan rekurens.
- Basis bisa dikatakan kondisi awal dari fungsi rekurens. Ketika fungsi telah punya nilai di suatu parameter tertentu, itulah yang disebut basis. Basis bisa lebih dari satu nilai, bisa hanya memiliki satu nilai. Intinya basis ini yang jadi titik berhentinya pemanggilan fungsi.
- Rekurens adalah pemanggilan fungsi yang menuju basis dengan memanggil dirinya sendiri. Ketika nilai fungsi belum ada, maka kita gunakan rekurens untuk memanggil fungsi serupa yang menuju basis. Jika masih belum di basis, pemanggilan rekurens akan terus dilakukan sampai bertemu basis.
Contoh pada suku ke-N Fibonacci yaitu F(n) = F(n-1) + F(n-2). Bagian ini dinamakan rekurens fungsi.
Sedangkan untuk menentukan basis kita lihat bahwa fungsi di atas berhenti saat F(3) = F(2) + F(1), karena tidak mungkin dilakukan pemanggilan F(1) = F(0) + F(-1) karena bilangan Fibonacci terkecil yaitu bilangan ke-1 yaitu 1 (ada juga yang mendefinisikan bilangan Fibonacci dimulai Fibonacci ke-0 yaitu 0). Maka kita ambil basisnya F(1) = 1 dan F(2) = 1. (atau F(1) = 1 dan F(0) = 0 jika menggunakan definisi Fibonacci ke-0).
Dengan memanfaatkan definisi rekursif ini kita bisa implementasikan Fibonacci ke-N dengan fungsi rekursif seperti berikut.
function fibonacci (n : integer) : integer;
begin
if n<3 then
fibonacci := 1 { basis : suku pertama dan kedua bernilai 1 }
else
fibonacci := fibonacci(n-1)+fibonacci(n-2); { rekurens }
end;
Tapi ada kelemahan dalam pemanggilan fungsi seperti ini. Coba perhatikan skema pemanggilan fungsi di bawah!
Setiap pemanggilan F(n) akan memanggil F(n-1) dan F(n-2) meskipun F(n-2) juga telah dipanggil pada penghitungan F(n-1). Gambar di atas menunjukkan dalam pemanggilan F(5) saja F(3) dipanggil berulang-ulang, yaitu 2 kali. Begitupun dengan F(1) dan F(2). Coba bayangkan jika F(500) dipanggil! Maka F(1) dan F(2) akan dipanggil ribuan kali. Betapa tidak efektifnya program kita!!
Maka kita bisa menggunakan alternatif lain yaitu dengan memakai teknik Dynamic Programming.
Dynamic Programming (DP)
Kelemahan kita menggunakan rekursif biasa yang baru saja dibahas yaitu terjadinya overlapping subproblem, yaitu subproblem yang telah dihitung dicari lagi sehingga pemanggilan fungsi menjadi sangat boros. Dengan DP kelemahan rekursif yang satu ini bisa tercover.Inti dari DP adalah mengubah parameter menjadi state fungsi dan menyimpan setiap state yang dilalui fungsi dalam suatu struktur data. Sehingga sekali kita telah menghitungnya kita tidak perlu mengulanginya lagi.
Dalam membuat konstruksi DP kita dapat memakai 2 cara : top-down dan bottom-up.
1. DP Top-Down
Style yang satu ini cukup mudah. Dengan menggunakan fungsi rekursif yang sebelumnya dan sedikit modifikasi maka akan terbentuk DP top-down.
Jika kita lihat, kelemahan rekursi yang sebelumnya hanyalah pada kurangnya penyimpanan state sehingga menyebabkan overlap. Maka sekarang kita akan menyimpan nilai semua state F(n) pada suatu variabel (misal array) yang kita namakan variabel memo sehingga kita tidak perlu menghitung berulang-ulang. Metode ini disebut memoization/memoisasi.
Coba perhatikan ilustrasi di bawah!
var fibo : array[1..1000] of integer; { variabel memo }
{ anggap array fibo telah diinisiasi nilai 0 }
function fibonacci (n : integer) : integer; { fungsi rekursif }
begin
if n<3 then
fibonacci := fibo[n] := 1
else if fibo[n]=0 then
fibonacci := fibo[n] := fibonacci(n-1)+fibonacci(n-2)
else
fibonacci := fibo[n];
end;
2. DP Bottom-Up
Jika DP top-down membuat solusi dengan fungsi rekursif (yang cenderung mengecil ke basis), maka DP bottom-up membuat solusi dari basis lalu membesar ke state berikutnya sampai batas yang diinginkan. Bisa dikatakan style ini kebalikan dari style sebelumnya.
Coba perhatikan ilustrasi berikut!
Implementasinya cukup dengan iterasi biasa untuk mengisi F(3) sampai F(n) sehingga masih cukup mudah dibuat. Dan karena implementasinya bebas rekursi maka untuk Fibonacci dengan urutan yang sangat besar (contoh: F(2000,000,000)) tidak akan mengalami stack overflow ketika pemanggilannya seperti terjadi pada fungsi rekursi. Inilah keunggulan utama DP bottom-up dibanding top-down. Meskipun kadang implementasi bottom-up umumnya lebih susah dari top-down karena dimulai dari basis dan pemilihan rekurens yang harus ekstra hati-hati (karena bisa jadi tidak semua parameter memo digunakan dalam DP). Pengalaman saya sendiri saat ICPC kemarin tim saya harus bergelut selama hampir sejam untuk mendebug solusi DP bottom-up karena ada bagian yang harusnya tidak dimasukkan rekurens ternyata belum dikecualikan.
Kurang lebih implementasinya seperti berikut.
var fibo : array[1..1000] of integer; { variabel memo }
begin {program utama}
fibo[1]:=1; { inisiasi basis }
fibo[2]:=1;
for i:=3 to n do { pengisian memo dengan iterasi }
fibo[i]:=fibo[i-1]+fibo[i-2];
{ output fibo[n] jika perlu }
end.
Dan perlu diketahui untuk kedua solusi DP di atas memiliki kompleksitas \(O(N)\), yaitu linear terhadap nilai N. Sehingga untuk N < 100 juta, runtime yang dibutuhkan masih sekitar 1 detik atau kurang.
Untuk N yang sangat besar kita tidak dapat memakai solusi ini karena pasti akan mendapat verdict TLE karena runtime yang dibutuhkan bisa 100 detik atau malah jauh lebih besar. Maka ada cara yang lebih baik menggunakan teknik Divide and Conquer dengan perkalian matriks.
Tunggu di post berikutnya :
About Fibonacci : Divide and Conquer Approach; Matrix Exponentiation- part 3
Tidak ada komentar:
Posting Komentar