Kompleks Analisis Deret Fibonacci

Coding Interview dari Junior sampai Senior

Latar belakang saya menulis dan menganalisis deret fibonacci ada dua alasan. Pertama, saya adalah salah seorang pemuja deret ini karena golden ratio yang disebut angka Tuhan phi = 1,618… .

Kedua, saya pernah gagal diproses coding interview. Saya gagal karena cuma dapat menjawab level junior saja dari deret fibonacci ini. Kesalahan saya waktu itu karena, pertama tidak berniat untuk melakukan coding interview, kedua konon kata orang jika akan melakukan coding interview harus melakukan persiapan dengan membaca algoritma dari kasus-kasus yang sering dijadikan bahan untuk interview.

Dengan alasan di atas saya berusaha membuka tabir mengenai deret fibonacci. Mudah-mudahan tulisan dapat menjadi sumber rujukan bagi orang-orang yang akan melakukan coding interview khususnya mengenai algoritma deret fibonacci.

Apa Itu Deret Fibonacci

Deret Fibonacci adalah deret aritmatika yang terdiri dari serangkaian deret angka sederhana yang susunan angkanya merupakan penjumlahan dari dua angka sebelumnya (0,1,1,2,3,5,8,13,21,…dst) rumus deret Fibonacci bisa ditulis sebagai berikut Un = Un-2 + Un-1, artinya suku ke-n merupakan penjumlahan dari dua suku sebelumnya.

Kemudian seorang matematikawan barat yang berasal dari Italia, Leonardo “Fibonacci” Da Pisa (1170–1250,) mengadaptasi dan mengembangkan deret ajaib ini untuk menghitung pola perkembangbiakan kelinci yang ia amati dan tuliskan dalam buku karangannya yang berjudul Liber Abaci.

Pada awalnya para ilmuwan menganggap remeh pengkajian Fibonacci mengenai deret angka ini karena dianggap hanya sebuah teka-teki matematika saja, Hingga akhirnya pada abad ke-19 Eduard Lucas menyadari berbagai keunikan deret angka ini dan mempelajarinya lebih lanjut.

Menentukan Solusi dengan Cara Rekursif

Solusi pertama yang paling mudah untuk mencari nilai ke- N dari deret fibonacci adalah dengan cara rekursif. Biasanya ini adalah solusi yang bisa dihasilkan dengan mudah.

Fibonacci(0) = 0, 
Fibonacci(1) = 1,
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

Apabila kita analisis berdasarkan Big O Notation maka tingkat kompleksitasnya lumayan tinggi. Waktu eksekusi akan meningkat secara eksponensial karena proses rekursif yang terjadi.

Penerapan Solusi Code

Berikut adalah solusi dalam bahasa Java.

Menentukan Solusi dengan Cara Pengulangan

Solusi kedua adalah dengan cara pengulangan atau iterasi. Dengan proses iterasi kita akan mendapatkan tingkat kompleksitas yang cukup lumayan karena solusi bersifat linear.

Algoritma dalam solusi iterasi ini membutuhkan waktu linier untuk menyelesaikannya. Pada dasarnya kita melakukan iterasi melalui loop sebanyak n-2 kali, jadi Big O (notasi yang digunakan untuk menggambarkan skenario kasus terburuk) akan sama dengan O (n)dalam kasus ini. Kompleksitas ruang adalah O(n).

Penerapan Solusi Code

Berikut adalah solusi dalam bahasa Java.

Solusi ini berada dalam O(n)kompleksitas waktu linier dan O(1)kompleksitas ruang konstan. Jumlah loop yang diperlukan untuk menghitung bilangan fib ke-n akan tetap meningkat pada laju linier ketika n bertambah, tetapi kita menimpa bilangan sebelumnya dalam urutan saat kita membangunnya, membuat kompleksitas ruang konstan untuk masukan n apa pun. Ini juga disebut Pendekatan Atas-Bawah Iteratif .

Solusi dengan Binet Formula

Dengan menggunakan rumus Binet kita dapat menyelesaikan deret fibonacci ini tanpa menggunakan rekursif atau pun pengulangan. Dengan demikian kita akan mendapatkan kompleksitas waktu yang lebih bagus yaitu logaritma.

Dengan asumsi bahwa operasi matematika primitif (+, -, * dan /) adalah O(1)kita dapat menggunakan hasil ini untuk menghitung bilangan fibonacci ke- O(log n)waktu ( O(log n)karena eksponen dalam rumus).

Penerapan Solusi Code

Berikut adalah solusi dalam bahasa Java.

Solusi dengan Tail Rekursif

Dalam rekursif tradisional, kita melakukan panggilan rekursif, mengambil nilai kembali dari panggilan tersebut dan menghitung hasilnya. Kita mendapatkan hasil perhitungan hanya sampai kita kembali dari setiap pemanggilan rekursif, yang membutuhkan banyak ruang pada tumpukan pemanggilan.

Pada tail rekursif kita menghitung hasil pertama, kemudian mengirimkan hasil tadi ke proses pemanggilan selanjutnya. Kompleksitas baik secara waktu dan ruang adalah sangat baik yaitu konstan O(n).

Penerapan Solusi Code

Berikut adalah solusi dalam bahasa Java.

Perlu diperhatikan kita menggunakan jenis data int. Apabila nilai fibonacci yang dicari semakin besar kita harus menggunakan type data dengan rentang yang panjang misal kan type data long atau double.

Itu lah beberapa solusi deret fibonacci mulai dari level junior sampai senior. Terdapat beberapa solusi lain yang saya menyebutkan solusi yang dihasilkan oleh para expert sebut saja teknik pencarian dengan sorting, pendekatan matriks, dan ES6 generator. Mungkin suatu saat kita coba membahasnya.

References

1. https://www.sciencedirect.com/science/article/pii/S0195669807000595#
2. https://medium.com/the-legend/big-o-notation-d7def34eaed8
3. https://medium.com/plus-minus/big-oh-for-algorithms-7fdb1d2f35d
4. https://www.idntimes.com/science/discovery/vini-krisdiani/fakta-deret-angka-fibonacci-c1c2/6

Sponsor

Membutuhkan kaos dengan tema pemrograman :

Kafka T-shirt

Elastic T-shirt

Dapat menghubungi The Legend.