Thuật Toán Interpolation Search

 

Bài hôm nay chúng ta cùng tìm hiểu về thuật toán Interpolation Search (tìm kiếm nội suy)

1. Nguyên lý cơ bản của Interpolation 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.

+ Tìm kiếm nội suy là một sự cải tiến của tìm kiếm nhị phân Binary Search.

+ Nếu như tìm kiếm nhị phân luôn nhắm vào vị trí giữa của các khoảng tìm kiếm thì tìm kiếm nội suy lại có xu hướng tiến gần đến vị trí gần với giá trị tìm kiếm.

+ Do đó Tìm kiếm nội suy đạt được sự tối ưu rất cao, và tốc độ nhanh hơn nhiều Binary.

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

Giả sử nếu số phần từ n = 1 tỷ

=> Linear O = 1 tỷ.

=> Binary O = log2(1 tỷ) xấp xỉ =  30

=> Nội suy O =  log2(log2(1 tỷ)) < 5

Các bạn sẽ thấy chỉ với số lượt nhỏ hơn 5, Tìm kiếm nội suy có thể tìm cho bạn được vị trí cần tìm trong 1 tỉ phần tử

=> RẤT KHỦNG.

Do đó nó được coi như hàng độc, và khi nào cần thiết thì mới sử dụng.

Vậy thì cơ chế nào để tìm kiếm nội suy có thể đạt được tốc độ kinh khủng như vậy.

Bí quyết của nó là tìm ra phần tử gần với giá trị tìm kiếm nhất và bắt đầu từ đó thể tìm.

Ví dụ bạn có 1 danh sách tập hợp các thành viên trong một công ty đã xắp xếp theo thứ tự a – b- c

Giả sử chúng ta cần tìm người tên là Thanh, thì chúng ta sẽ ưu tiên việc tìm từ cuối danh sách chứ ko dại gì mò từ đầu danh sách.

Suy ra chúng ta phải tìm được phần tử cuối danh sách mà gần với phần tử tìm kiếm tên Thanh.

Giả sử ta có: left , right là hai vị trí đầu cuối, T là tập, X là giá trị cần tìm.

Step 1:

Bắt đầu từ công thức tìm phần từ chính giữa của tập theo Binary Search ta có

pos = left + (right – left)* 1/2;

Ta sẽ cải tiến bằng các thay giá trị 1/2 bằng biểu thức sau:  (X – T[left])/(T[right] – T[left])

Như vậy pos = left + (X- T[left]) * (right – left) / (T[right] – T[left])

Pos chính là vị trí dò tìm được mà nó khá gần so với giá trị X cần tìm.

Step 2:

Kiểm T[pos] nếu bằng X thì pos là vị trí cần tìm.

Nếu nhỏ hơn X thì ta tăng left lên một đơn vị và tiếp tục thực hiện lại bước 1

Nếu lớn hơn X thì ta giảm right một đơn vị và tiếp tục thực hiện lại bước 1

2 Thực hành Thuật toán interpolation 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 InterpolationSearch.

// Phattrienphanmem123az.com
#include <iostream>
#include <conio.h>

int InterPolationSearch(int arr[], int n, int x)
{
  int left = 0;
  int right = n-1;
  while (left <= right && x >= arr[left] && x <= arr[right])
  {
    double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
    int val2 = (right-left);
    int pos = left + val1*val2;

    if (arr[pos] == x)
      return pos;

    if (arr[pos] < x)
      left = pos + 1;
    else
      right = pos - 1;
  }
  return -1;
}

Hàm Main

int main(int argc, _TCHAR* argv[])
{
  int arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
  int n = sizeof(arr)/sizeof(arr[0]);

  int x = 35;
  int index = InterPolationSearch(arr, n, x);

  if (index != -1)
    std::cout << "Element found at index:" << index;
  else
    std::cout << "Element not found.";

  _getch();
	return 0;
}

Về cơ bản tìm kiếm nội suy là một kỹ thuật đạt được tốc độ rất cao và nhanh. Do đó nó như là thuốc mạnh liều cao, nên dùng cho những trường hợp phù hợp.

Ví dụ với những tập có số lượng phần từ nhỏ, đối tượng phần tử đơn giản thì ko cần thiết phải sử dụng tìm kiếm nội suy. Mà chỉ nên dùng tìm kiếm nội suy cho những tập có số lượng phần tử lớn, đối tượng phần tử phức tạp, mất nhiều thời gian xử lý.

TPham