Algoritma JavaScript: Memecahkan Urutan Fibonacci (LeetCode)

Angka- angka Fibonacci , umumnya dilambangkan F(n)membentuk urutan, yang disebut deret Fibonacci , sehingga setiap angka adalah jumlah dari dua angka sebelumnya, dimulai dari 0dan 1. Bilangan pada barisan bilangan bulat berikut 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Itu adalah

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Contoh 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

Ada beberapa opsi untuk memecahkan masalah ini: Pendekatan Rekursi.

Pendekatan Rekursi

Sebuah metode sederhana yang merupakan implementasi rekursif matematis relasi rekursif langsung. Cara paling lambat untuk menyelesaikan masalah ini karena membutuhkan kompleksitas waktu eksponensial : O(2^N) dan kompleksitas ruang : O(N) .

Pemrograman Dinamis menggunakan memoisasi (pendekatan Top down)

Kita dapat menghindari pekerjaan berulang yang dilakukan secara rekursif dengan menyimpan angka Fibonacci yang dihitung sejauh ini. Kami hanya perlu menyimpan semua nilai di peta. Kompleksitas waktu : O(N) dan kompleksitas ruang : O(N) .

Pendekatan Iterasi

Iterasi, dengan menyelesaikan semua sub-masalah dan mengembalikan jawaban untuk elemen N, menggunakan nilai Fibonacci yang sudah dihitung. Kompleksitas waktu : O(N) dan kompleksitas ruang : O(N) .

Pendekatan Iterasi ( Dioptimalkan Ruang)

Kita dapat mengoptimalkan pendekatan iterasi dengan menyimpan dua angka sebelumnya hanya karena hanya itu yang kita perlukan untuk mendapatkan angka Fibonacci berikutnya secara berurutan. Kompleksitas waktu : O(N) dan kompleksitas ruang : O(1) .

Pendekatan Matriks Eksponensial

Gunakan Eksponensial Matriks untuk mendapatkan angka Fibonacci dari elemen di (0, 0) dalam matriks yang dihasilkan. Untuk melakukan ini, kita dapat mengandalkan persamaan matriks untuk deret Fibonacci, untuk menemukan bilangan Fibonacci ke-N :

Bagaimana cara kerja rumus ini Anda dapat melihat di Wiki

Solusi ini memiliki: kompleksitas waktu : O(logN) dan kompleksitas ruang : O(logN) .

Pendekatan Matematika

Kita dapat menggunakan golden ratio forumula:

Berikut tautan untuk mengetahui lebih lanjut tentang cara kerja deret Fibonacci dan rasio emas.

Solusi ini memiliki: kompleksitas waktu : O(logN) dan kompleksitas ruang : O(1) .

Juga, terkadang diperlukan untuk mengembalikan bukan nilai untuk N yang diberikan, tetapi untuk mengembalikan array elemen Fibonacci hingga N yang diberikan.

Contoh:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

dan Pemrograman Dinamis menggunakan memoisasi dengan sedikit perubahan:

Kami telah mempertimbangkan opsi yang berbeda untuk memecahkan masalah Fibonacci, yang paling sulit dipahami adalah Eksponensial Matriks, tetapi biasanya pengetahuan tentang 4 metode sebelumnya sudah cukup untuk wawancara.

Semoga bermanfaat untuk Anda!

Terima kasih sudah membaca! Sampai jumpa lagi.

Lebih banyak konten di PlainEnglish.io . Mendaftar untuk buletin mingguan gratis kami . Ikuti kami di Twitter , LinkedIn , YouTube , dan Discord . Tertarik dengan Peretasan Pertumbuhan? Lihat Sirkuit .