Tổng quan
Fibonacci Search thu hẹp một khoảng đã sắp bằng cách dùng các số Fibonacci làm điểm chia thay vì chia đôi. Mọi vị trí dò đều đạt được bằng phép cộng hai số Fibonacci trước đó, nên thuật toán không cần phép chia lẫn phép nhân — chỉ cộng và trừ.
Đó từng là lợi thế thật trên phần cứng mà phép chia đắt hơn phép cộng nhiều lần. Nó còn một tính chất thứ hai bền hơn: hai khoảng ứng viên mà nó có thể chuyển vào có kích thước không bằng nhau, và nó luôn bước theo lượng nhỏ hơn, nên mẫu truy cập bộ nhớ của nó cục bộ hơn binary search — lý do nó vẫn xuất hiện ở những nơi dữ liệu nằm trên băng từ, đĩa, hoặc bất cứ thứ gì có chi phí di chuyển đầu đọc cao.
Fibonacci Search hoạt động thế nào?
- Tìm số Fibonacci F(k) nhỏ nhất lớn hơn hoặc bằng độ dài mảng.
- Giữ hai số Fibonacci ngay dưới nó và dùng chúng để tính chỉ số dò gần đầu khoảng hiện tại.
- So sánh mục tiêu với giá trị tại điểm dò đó. Nếu khớp thì dừng.
- Nếu mục tiêu lớn hơn, dịch mốc lên tới điểm dò và trượt bộ ba Fibonacci xuống một bậc; nếu nhỏ hơn, giữ nguyên mốc và trượt bộ ba xuống hai bậc.
- Lặp lại cho tới khi các số Fibonacci về tới đáy dãy, rồi kiểm tra phần tử duy nhất còn lại.
Khi nào nên dùng?
- Tìm kiếm trên phương tiện mà truy cập không tuần tự đắt đỏ — băng từ, đĩa quay, hay dữ liệu phân trang — nơi tính cục bộ quan trọng hơn số vòng.
- Môi trường nhúng hoặc số dấu chấm cố định, nơi phép chia số nguyên chậm hoặc không có sẵn.
- Làm người anh em của golden-section search, phiên bản liên tục dùng để tối ưu các hàm đơn điệu-một-đỉnh.
- Hiếm khi đáng dùng trong code chạy trong bộ nhớ thông thường — binary search đơn giản hơn và phép chia rất rẻ trên CPU hiện đại.
Phân tích độ phức tạp
Thời gian là O(log n): mỗi bước thu khoảng còn khoảng 1/φ kích thước, với φ ≈ 1,618, cho ra log_φ n ≈ 1,44·log₂ n bước. Vậy nó cần thêm vài lần dò so với binary search nhưng mỗi lần chỉ tính bằng phép cộng. Bộ nhớ là O(1) — ba số Fibonacci và một mốc. Mảng phải đã sắp và truy cập được theo chỉ số bất kỳ, đúng điều kiện mà binary search cũng cần.
Câu hỏi thường gặp
Vì sao lại là các số Fibonacci?
Vì F(k) = F(k−1) + F(k−2) nghĩa là mọi chỉ số bạn cần đều là tổng của các số bạn đã có sẵn. Tỉ lệ chia rơi ra từ đó là tỉ lệ vàng, cũng chính là tỉ lệ khiến hai khoảng kế tiếp khả dĩ tái sử dụng được mà không phải tính lại gì.
Nó có nhanh hơn binary search không?
Không, xét theo số phép so sánh — nó dò nhiều hơn khoảng 44%. Nó vẫn có thể thắng trên phần cứng mà một phép chia đắt hơn phần chênh lệch đó, hoặc nơi tính cục bộ chặt hơn của nó tránh được lỗi cache và lần tìm trên đĩa.
Độ dài mảng có bắt buộc là số Fibonacci không?
Không. Thuật toán chọn số Fibonacci đầu tiên lớn hơn hoặc bằng độ dài và kẹp lại mọi điểm dò rơi ra ngoài mảng, nên độ dài bất kỳ vẫn chạy được mà không cần chèn thêm.