Thuật Toán Jump Search

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Jump Search (Thuật toán tìm kiếm nhảy)

1. Nguyên lý cơ bản của Jump Search

Cũng giống như giải thuật Binary Search. Jump Search cũng yêu cầu danh sách đã cho phải là một danh sách đã được sắp xếp theo thứ tự đã biết.

Ví dụ là tăng dần.

Cơ chế của Jump Search đó là tìm ra một hệ số nhảy được tính bằng : Căn bậc hai của số phần tử.

Từ hệ số tìm được, Jump Search sẽ thực hiện nhảy phần tử theo hệ số để tìm ra phần từ lớn hơn giá trị tìm kiếm.

=> Phần tử tìm kiếm sẽ nằm trong khoảng của nhảy mà chứa phần từ lớn hơn giá trị tìm kiếm ở trên.

Minh Họa hình vẽ như sau:

Tôi có tập 9 phần từ đã được sắp xếp theo thứ tự tăng dần.

Tôi xác định giá trị nhảy là step = √9 = 3 .

Giả sử giá trị cần tìm là 33.

Sử dụng một biến prev để lưu vị trí bắt đầu.

Một biến jump để nhảy.

Step 1:

Prev = 0, jump =step = 3

Kiểm tra T[jump – 1] => T[2] = 6 < 33 =>Nhảy step 2.

Step 2:

Gán prev = jump = 3.

Nhảy jum theo step => jum = jump + step = 6

Tiếp tục kiểm tra T[jum -1] => T[5] = 13 < 33 => Nhảy step 3

Step 3:

Gán prev = jump = 6

Nhảy jump = jump + step = 9  (bằng số phần tử, nếu jum lớn hơn n thì gán jum = n)

Lại kiểm tra T[jump – 1] => T[8] = 44 > 33 => Đã tìm được khoảng chứa giá trị cần tìm.

Khoảng chứa giá trị cần tìm là từ prev = 6 , jump = 9.

Lúc này chúng ta chỉ việc kiểm tra tuyến tính tệp từ vị trí prev đến jump để tìm ra giá trị cần tìm.

Sử dụng for hoặc while để duyệt phần tử trong khoảng prev – jump.

2. Các tính chất thuật toán.

– Tập cần tìm kiếm là phải được xắp xếp trước và biết rõ theo chiều tăng giảm.

– ĐỘ PHỨC TẠP HAY THỜI GIAN THỰC THI CỦA THUẬT TOÁN LÀ: O = √(n) 

3 Thực hành Jump Search

Bây giờ từ nguyên lý ở trên chúng ta sẽ cùng thực hành với code c++

Hàm JumpSearch

Hàm Main

Ok. Đó là nguyên lý cơ bản của JumpSearch.

Về cơ bản thì độ phức tạp thời gian của Jump Search nằm giữa Linear Search (cách tìm kiếm duyệt phần từ thông thường)   và Binary Search.

TPham

 

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.