Thuật toán chuỗi Fibonacci △

1760

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.

Có thể bạn quan tâm

  Thế nào là một Requirement tốt?
  Stateless là gì? Stateful là gì?

Statement
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ó.

First implementation
Vì vậy, bây giờ chúng ta sẽ implement đoạn code đầu tiên, chúng ta sẽ sử dụng một vòng lặp đơn giản để đi đến lời giải.

Đâ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ũ.
Và tin tốt là nó có độ phức tạp O(n). Nhưng bây giờ hãy để thử xem một số cách khác để tiếp cận vấn đề.

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 đó.

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).

Video: Thiết kế hệ thống chịu lỗi cao và tối ưu tốc độ với AWS

Bendmark
Sử dụng 50 làm số đầu vào và so sánh 3 cách trên:

While loop

  • Time complexity: O(N)
  • Space complexity: Constant
  • Function calls: 51
  • Time needed: 0.000001ms

Recursion

  • Time complexity: O(2^N)
  • Space complexity: O(n)
  • Function calls: 20.365.011.074
  • Time needed: 176.742ms

Memoization

  • Time complexity: O(2N)
  • Space complexity: O(n)
  • Function calls: 99
  • Time needed: 0.000001ms

Kết luận
Đây chỉ là một ví dụ về cách thiết kế, cải thiện và phân tích thuật toán, trong trường hợp này là chuỗi Fibonacci, đủ đơn giản để hiểu và đáng ngạc nhiên khi thấy hiệu suất tăng mà ta đạt được chỉ với một số thay đổi nhỏ.

Một số cách tiếp cận khác
Chúng ta có thể dùng công thức Binet để tính số fibonacci thứ N.

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, cũng khá đơn giản thôi, với độ phức tạp O(logN)

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é. △

TopDev via Viblo