Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”, nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching” không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài ra đây cũng là một nội dung được đề cập trong TAoCP - Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link). Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP - Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ lưu trữ ngoại vi trở nên tốn kém ( link ). Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần References. Một phiên bản cải tiến với kích thức mảng $N$ bất kì sẽ được update sau.

Input: mảng $K_1, K_2, ..., K_N$ được sắp xếp và phần tử $K$ cần tìm. Giả sử
$N+1 = F_{k+1}. Lưu ý index của mảng bắt đầu 1$

P1. [Khởi tạo] i = F[k], p = F[k-1], q = F[k-2]
P2. [So sánh].
    if K[i] < K: go to P3.
    else if K[i] > K: go to P4.
    else: return i;
P3. [Xét cây con Fibonacci bên trái]
    if q = 0: return -1
    else:
        i -= q
        (p, q) = (q, p-q)
        go to P2
P4. [Xét cây con Fibonacci bên phải]
    if p = 1: return -1
    else:
        i += q
        p -= q
        q -= p
        go to P2

Bài tập

• Thiết kế thuật toán cho trường hợp $N \geq 0$.
• Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với $F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),¹ cây Fibonacci được xây dựng như sau:

1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử ($N+1=F_{k+1} = F_7 = 13$)), số internal nodes $F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra, ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có $F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể” có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$ nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer recurrence. Nếu sử dụng Akra-Bazzi method thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

• C implementation: cá nhân mình nghĩ đây là bản cài đặt khá chuẩn rồi.
• Knuth, Donald Ervin. The art of computer programming. Vol. 3. Pearson Education, 1997.[ aka TAoCP in my blog]
• Sedgewick, Robert, and Kevin Wayne. Algorithms. Addison-Wesley Professional, 2011.
• GeeksforGeeks’s Fibonaccian Searching.
• Wiki.

TODO

• Minh họa cây Fibonacci.
• Phiên bản C++.
• So sánh độ phức tạp với tìm kiếm nhị phân, tổng quát hóa bài toán.
  • Hằng số $b$.