Thuật toán JavaScript: Giải dãy Fibonacci(LeetCode)

Nov 24 2022

Sự miêu tả

Các số Fibonacci, thường được ký hiệu là F(n) tạo thành một dãy, được gọi là dãy Fibonacci, sao cho mỗi số là tổng của hai số đứng trước, bắt đầu từ 0 và 1. Các số trong dãy số nguyên sau 0, 1, 1 , 2, 3, 5, 8, 13, 21, 34, 55, 89,…….

Ảnh của Ludde Lorentz trên Bapt

Các số Fibonacci , thường được biểu thị F(n)dưới dạng một dãy, được gọi là dãy Fibonacci , sao cho mỗi số là tổng của hai số đứng trước, bắt đầu từ 0và 1. Các số trong dãy số sau 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,……..

Đó là

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

Ví dụ 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

Có một số tùy chọn để giải quyết vấn đề này: Phương pháp đệ quy.

Phương pháp đệ quy

Một phương pháp đơn giản là một quan hệ truy hồi toán học thực hiện đệ quy trực tiếp. Cách chậm nhất để giải quyết vấn đề này vì nó cần độ phức tạp thời gian theo hàm mũ : O(2^N) và độ phức tạp không gian : O(N) .

Lập trình động sử dụng ghi nhớ (Cách tiếp cận từ trên xuống)

Chúng ta có thể tránh lặp lại công việc được thực hiện trong đệ quy bằng cách lưu trữ các số Fibonacci đã tính cho đến thời điểm này. Chúng ta chỉ cần lưu trữ tất cả các giá trị trong bản đồ. Độ phức tạp thời gian : O(N) và độ phức tạp không gian : O(N) .

Phương pháp lặp

Lặp lại, với việc giải quyết tất cả các vấn đề phụ và trả về câu trả lời cho phần tử N, sử dụng các giá trị Fibonacci đã được tính toán. Độ phức tạp thời gian : O(N) và độ phức tạp không gian : O(N) .

Phương pháp lặp lại ( Tối ưu hóa không gian)

Chúng ta có thể tối ưu hóa phương pháp lặp chỉ lưu trữ hai số trước đó vì đó là tất cả những gì chúng ta cần để có được số Fibonacci tiếp theo trong chuỗi. Độ phức tạp thời gian : O(N) và độ phức tạp không gian : O(1) .

Phương pháp lũy thừa ma trận

Sử dụng Phép lũy thừa ma trận để lấy số Fibonacci từ phần tử tại (0, 0) trong ma trận kết quả. Để làm được điều này, chúng ta có thể dựa vào phương trình ma trận của dãy Fibonacci, để tìm số Fibonacci thứ N :

Công thức này hoạt động như thế nào, bạn có thể xem tại Wiki

Giải pháp này có: độ phức tạp thời gian : O(logN) và độ phức tạp không gian : O(logN) .

Phương pháp toán học

Chúng ta có thể sử dụng golden ratio forumula:

Đây là một liên kết để tìm hiểu thêm về cách hoạt động của dãy Fibonacci và tỷ lệ vàng.

Giải pháp này có: độ phức tạp thời gian : O(logN) và độ phức tạp không gian : O(1) .

Ngoài ra, đôi khi nó được yêu cầu không trả về một giá trị cho một N đã cho, mà trả về một mảng các phần tử Fibonacci cho đến một N nhất định.

Ví dụ:

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

và Lập trình động sử dụng ghi nhớ với ít thay đổi:

Chúng tôi đã xem xét các phương án khác nhau để giải bài toán Fibonacci, khó hiểu nhất là Phép lũy thừa ma trận, nhưng thông thường kiến thức về 4 phương pháp trước là đủ cho một cuộc phỏng vấn.

Hy vọng nó hữu ích cho bạn!

Cảm ơn vì đã đọc! Hẹn sớm gặp lại.

Thêm nội dung tại PlainEnglish.io . Đăng ký nhận bản tin miễn phí hàng tuần của chúng tôi . Theo dõi chúng tôi trên Twitter , LinkedIn , YouTube và Discord . Quan tâm đến hacking tăng trưởng? Kiểm tra Mạch .