Fibonacci numbers đã trở thành một giới thiệu phổ biến để đệ quy cho sinh viên Khoa học Máy tính và có một lập luận mạnh mẽ rằng họ vẫn tồn tại trong tự nhiên. Vì những lý do này, nhiều người trong chúng ta đã quen thuộc với họ.Tại sao số Fibonacci có ý nghĩa quan trọng trong khoa học máy tính?
Chúng cũng tồn tại trong Khoa học Máy tính ở nơi khác; trong các cấu trúc và thuật toán dữ liệu hiệu quả đáng ngạc nhiên dựa trên trình tự.
Có hai ví dụ chính mà tôi suy nghĩ:
- Fibonacci heaps có tốt hơn khấu hao theo thời gian chạy hơn nhị thức đống.
- Fibonacci search chia sẻ thời gian chạy O (log N) với số nhị phân tìm kiếm trên một mảng được sắp xếp.
Có một số đặc tính đặc biệt của những con số này mang lại cho họ lợi thế hơn các chuỗi số khác không? Nó có phải là một chất lượng không gian? Họ có thể có những ứng dụng nào khác?
Có vẻ lạ đối với tôi vì có rất nhiều chuỗi số tự nhiên xảy ra trong các vấn đề đệ quy khác, nhưng tôi chưa bao giờ thấy một đống Catalan.
Không quen thuộc sẽ là yếu tố lớn nhất? – Cyclone
Tôi nghĩ rằng loại câu hỏi này thuộc về cstheory hoặc math SE. Hấp dẫn, nhưng OT. –
@larsmans Không đồng ý. Một trong những câu hỏi thú vị nhất tôi đã thấy gần đây, và sự liên quan của nó được ủng hộ bởi thực tế là lập trình viên, chúng ta thấy nó ở mọi nơi. – Mike