Thuật Toán Exponential Search

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Exponential Search (Thuật toán tìm kiếm theo số mũ)
1. Nguyên lý Exponential Search

+ Cũng yêu cầu dãy số đầu vào là một dãy đã được xắp xếp cho sẵn.

+ Kết hợp với việc tìm kiếm theo kiểu nhị phân.

+ Tìm ra khoảng con chứa giá trị cần tìm kiếm, và sau đó sử dụng tìm kiếm nhị phân cho khoảng con đó.

Độ phức tạp thời gian mà nó đạt được là: Log2(n).

Step 1:

 

+ Kiểm tra phần tử 0 của tập để xem nó có phải là phần tử tìm kiếm hay không.

+ Nếu không thì bắt đầu giá trị chạy từ 1 và kiểm tra nó < giá trị cần tìm hay không.

=> Nếu có, thì tiếp tục tăng giá trị chạy lên theo công thức : i = i*2;

=> Nếu không, thì chứng tỏ giá trị cần tìm đang năm trong khoảng từ i/2 đến i  

Vì a[i] > X và vòng lặp trước đó là a[i/2] < X.

Do đó ta tìm được khoảng con chứa giá trị X cần tìm

Step 2:

Áp dụng Binary Search cho khoảng con vừa tìm được.

2 Thực hành.

+ Phù hợp cho việc tìm kiếm các mảng có số lượng phần tử lớn, hoặc phần từ tìm kiếm nằm gần đầu danh sách, (Nhanh tìm ra tập còn chứa giá trị tìm kiếm).

_______________________________________________________

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.