Tìm kiếm và sắp xếp luôn là một trong những điều cốt lõi cần biết và cải thiện. Giống như sắp xếp, tìm kiếm cũng nhận được sự chú ý đặc biệt từ các nhà khoa học máy tính. Hôm nay chúng ta sẽ tìm hiểu về một thuật toán tìm kiếm đặc biệt có tên là Wikipedia sort.
Tìm kiếm Fibonacci
Phương pháp tìm kiếm Fibonacci là một kỹ thuật tìm kiếm một mảng được sắp xếp bằng thuật toán chia và chinh phục để nén các vị trí có thể với sự trợ giúp của các số Fibonacci. So với tìm kiếm nhị phân, trong đó mảng được sắp xếp được chia thành hai mảng có kích thước bằng nhau, một trong số đó được tìm kiếm thêm, tìm kiếm Fibonacci chia mảng thành hai phần có kích thước là các số Fibonacci liên tiếp. Trung bình, điều này dẫn đến việc so sánh được thực hiện nhiều hơn khoảng 4%, mặc dù nó có công là người ta chỉ cần cộng và trừ để tính các chỉ số của các phần tử mảng được truy cập. Hơn nữa, tìm kiếm nhị phân truyền thống cần các hoạt động dịch chuyển bit, chia hoặc nhân mà ít phổ biến hơn tại thời điểm tìm kiếm Fibonacci lần đầu tiên được giới thiệu. Tìm kiếm Fibonacci có độ phức tạp trung bình và trường hợp xấu nhất là O (log n). Để thảo luận thêm, chuỗi Fibonacci có thuộc tính rằng một số là tổng của hai loạn luân của nó. Do đó trình tự có thể được tạo ra bằng cách thêm lặp đi lặp lại. Tìm kiếm nhị phân hoạt động bằng cách chia khu vực tìm kiếm thành các phần bằng nhau (1: 1). Tìm kiếm Fibonacci có thể chia nó thành các phần tiếp cận 1: 1.618 trong khi sử dụng các hoạt động đơn giản hơn.
Thuật toán
Chúng tôi giả định rằng mảng được sắp xếp quản trị là mảng và chúng tôi muốn tìm phần tử và chúng tôi sẽ sử dụng các bước sau để tìm phần tử với các bước tối thiểu:
Đầu tiên, tìm kiếm số Fibonacci nhỏ nhất lớn hơn hoặc bằng n. Đặt số này là fb (M) [số Fibre thứ m]. Đặt hai số Fibonacci trước nó là fb (M-1) [(m-1) 'số Fibonacci] và fb (M-2) [(m-2)' số Fibonacci].
Trong khi mảng có các phần tử cần kiểm tra:
-> phần tử so sánh với phần tử cuối cùng của phạm vi được bao phủ bởi fb (M-2)
-> Nếu phần tử bằng, trả về giá trị chỉ mục
-> Khác nếu phần tử nhỏ hơn phần tử, chuyển biến số Fibonacci thứ ba xuống hai mức Fibre xuống, biểu thị loại bỏ khoảng hai phần ba mảng không được nghiên cứu.
-> Phần tử khác lớn hơn phần tử, di chuyển biến Fibonacci thứ ba xuống một Fibonacci. Đặt lại offset cho chỉ mục. Kết quả này cùng nhau loại bỏ khoảng một phần ba phía trước của mảng không được nghiên cứu.
Vì có thể có một yếu tố duy nhất còn lại để so sánh, hãy kiểm tra xem fbMm1 có phải là '1' không. Nếu có, so sánh x với phần tử còn lại. Nếu khớp, trả về giá trị chỉ số.
Thực hiện
Thực hiện trong ruby như sau
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | <span class="token keyword">def</span> fibonacci_search int arr <span class="token punctuation">,</span> int element n <span class="token operator">=</span> n <span class="token punctuation">.</span> size f2 <span class="token operator">=</span> <span class="token number">0</span> f1 <span class="token operator">=</span> <span class="token number">1</span> f <span class="token operator">=</span> f2 <span class="token operator">+</span> f1 offset <span class="token operator">=</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">while</span> f <span class="token operator"><</span> n <span class="token keyword">do</span> f2 <span class="token operator">=</span> f1 <span class="token punctuation">;</span> f1 <span class="token operator">=</span> f <span class="token punctuation">;</span> f <span class="token operator">=</span> f2 <span class="token operator">+</span> f1 <span class="token punctuation">;</span> <span class="token keyword">end</span> <span class="token keyword">while</span> f <span class="token operator">></span> <span class="token number">1</span> <span class="token keyword">do</span> i <span class="token operator">=</span> <span class="token punctuation">[</span> offset <span class="token operator">+</span> f2 <span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">.</span> min <span class="token keyword">if</span> arr <span class="token punctuation">[</span> i <span class="token punctuation">]</span> <span class="token operator"><</span> element f <span class="token operator">=</span> f1 f1 <span class="token operator">=</span> f2 f2 <span class="token operator">=</span> f <span class="token operator">-</span> f1 offset <span class="token operator">=</span> i <span class="token keyword">elsif</span> arr <span class="token punctuation">[</span> i <span class="token punctuation">]</span> <span class="token operator">></span> element f <span class="token operator">=</span> f2 f1 <span class="token operator">=</span> f1 <span class="token operator">-</span> f2 f2 <span class="token operator">=</span> f <span class="token operator">-</span> f1 <span class="token keyword">else</span> <span class="token keyword">return</span> i <span class="token keyword">end</span> <span class="token keyword">end</span> <span class="token keyword">return</span> offset <span class="token operator">+</span> <span class="token number">1</span> <span class="token keyword">if</span> f1 <span class="token operator">&&</span> arr <span class="token punctuation">[</span> offset <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">==</span> element <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">end</span> |
Phức tạp
Từ thuật toán trên, người ta thấy rằng nếu chúng ta phải tìm kiếm phần lớn hơn của mảng thì thời gian chạy sẽ nhiều hơn và sẽ dẫn đến trường hợp xấu nhất và độ phức tạp của nó sẽ là O (log n). Nếu trong lần tìm kiếm đầu tiên, chúng ta có được phần tử của mình thì nó sẽ được coi là trường hợp tốt nhất và độ phức tạp sẽ là O (1). Khi chúng ta xem xét trường hợp trung bình thì trường hợp còn lại và nằm giữa i tốt nhất và xấu nhất khi chúng ta phải tìm kiếm phần tử trên phần nhỏ hơn của mảng và do đó chúng ta có độ phức tạp trường hợp trung bình là O (log n). Nếu phần tử đang được tìm kiếm có bộ nhớ truy cập không đồng nhất (nghĩa là thời gian cần thiết để truy cập vị trí lưu trữ khác nhau tùy thuộc vào vị trí được truy cập), tìm kiếm Fibonacci có thể có lợi thế hơn so với tìm kiếm nhị phân trong việc giảm nhẹ thời gian trung bình cần thiết để truy cập một vị trí lưu trữ. Nếu máy thực hiện tìm kiếm có bộ đệm CPU được ánh xạ trực tiếp, tìm kiếm nhị phân có thể dẫn đến nhiều lỗi bộ nhớ cache hơn vì các phần tử được truy cập thường có xu hướng tập hợp chỉ trong một vài dòng bộ đệm; điều này được giảm nhẹ bằng cách chia mảng trong các phần không có xu hướng là quyền hạn của hai. Nếu dữ liệu được lưu trữ trên một băng từ mà thời gian tìm kiếm phụ thuộc vào vị trí đầu hiện tại, sự đánh đổi giữa thời gian tìm kiếm dài hơn và so sánh nhiều hơn có thể dẫn đến một thuật toán tìm kiếm bị lệch tương tự như tìm kiếm Fibonacci.
Hy vọng điều này sẽ giúp Cảm ơn bạn Tham khảo: https://iq.opengenus.org/fiborie-search/