Xây dụng thuật toán tính tổng của n số Fibonacci đầu tiên
|
 Đã đăng vào thg 12 12, 2018 6:44 SA 4 phút đọc Bài đăng này đã không được cập nhật trong 3 năm Có lẽ là một trong những thuật toán nổi tiếng nhất từ trước đến nay, nhưng vẫn còn rất nhiều người phải gặp khó khăn khi cố gắng tìm một giải pháp hiệu quả. Hãy để mình giới thiệu cho bạn về chuỗi Fibonacci.
Cho 1 số N, trả về số fibonacci thứ N, trong đó chuỗi đó như sau: Sau khi xem qua, bạn có thể dễ dàng nhận thấy mỗi phần tử trong chuỗi là tổng của 2 phần tử liền trước nó. F(n) = F(n-1) + F(n-2)First implementation Đây có lẽ là giải pháp đầu tiên trong đầu của bạn. Phần quan trọng ở đây là chúng ta tính toán số tiếp theo bằng cách thêm số hiện tại vào số cũ. Dùng đệ quy Bây giờ hãy để xem nếu chúng ta có thể làm cho nó trông xịn hơn, bây giờ chúng ta sẽ sử dụng đệ quy để làm điều đó. function fibonacci(num) { if (num <= 1) return num; return fibonacci(num - 1) + fibonacci(num - 2); } Dễ đúng không? chúng ta chỉ giải quyết vấn đề trong 2 dòng code, nhưng hãy nhìn sâu hơn và xem những gì thực sự xảy ra. Base case: chúng ta chỉ cần kiểm tra xem giá trị nhỏ hơn 1 để trả về 2 trường hợp đầu tiên. Tin xấu là, chúng ta đã tăng độ phức tạp thời gian của thuật toán gần như là trường hợp xấu nhất. O(2^N), có nghĩa là việc triển khai hiện tại của chúng ta là theo cấp số nhân. Memoization Cuối cùng, và theo cách tiếp cận đệ quy, chúng ta sẽ sử dụng memoization để cải thiện độ hiệu quả của thuật toán. Thay đổi này sẽ tăng độ phức tạp không gian của thuật toán mới của chúng ta thành O (n) nhưng sẽ giảm đáng kể độ phức tạp thời gian xuống O(2N). function fibonacci(num, memo) { memo = memo || {}; if (memo[num]) return memo[num]; if (num <= 1) return num; return memo[num] = fibonacci(num - 1, memo) + fibonacci(num - 2, memo); } Bendmark Sử dụng 50 làm số đầu vào và so sánh 3 cách trên: While loop
Recursion
Memoization
Một số cách tiếp cận khác Hoặc chúng ta cũng có thể ứng dụng phép nhân ma trận, để hiểu kỹ hơn các bạn có thể google nó nhé, lý thuyết như hình bên dưới function multiply(mA, mB) { let m = [[], []]; for (let i = 0; i <= 1; i++) { for (let j = 0; j <= 1; j++) { m[i][j] = 0; for (let k = 0; k <= 1; k++) { m[i][j] = (m[i][j] + mA[i][k] * mB[k][j]); } } } return m; } function power(m, n) { if (n==1) return m; if (n%2!=0) return multiply(power(m, n-1) ,m); let r = power(m,n/2); return multiply(r, r); } Vậy thôi, qua đây mình cũng chỉ giới thiệu một số cách để giải, còn nhiều cách khác, hay ho hơn, xịn hơn các bạn có thể tự nghiên cứu thêm nhé. △ All rights reserved |
