Thuật toán tìm kiếm Tam Phân | Tổng quan về tìm kiếm tam phân

[neverland87]

Thuật toán tìm kiếm Tam Phân
Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày. Trong tin học nó đặt nền móng cho nhiều tác vụ tính toán quan trọng. Bài toán tìm kiếm là sự xác định vị trí của một hay nhiều phần tử, gọi là đối trị tìm kiếm (Argument), trong một bảng liệt kê có thứ tự các phần tử. Mỗi phần tử đơược đại diện bằng một khoá (Key) phục vụ cho tìm kiếm. Những ứng dụng của tìm kiếm thì rất đa dạng, cũng như có rất nhiều các thuật toán với đặc trương và hiệu suất khác nhau. Một trong những phơương pháp khá hiệu quả là phương pháp tìm kiếm Tam Phân.
Thuật toán tìm kiếm Tam Phân (Trisearch), xác định vị trí của phần tử cần tìm trong một bảng lệt kê các phần tử đươợc sắp xếp theo thứ tự tăng (hay giảm) dần của trường khoá. Bằng cách chia liên tiếp bảng liệt kê thành ba bảng liệt kê con có kích thơước tương đươơng nhau (Step=(R-L+1) div 3). Thuật toán này là sự thể hiện sinh động của tinh thần “chia để trị”. Giả sử bảng liệt kê đơược xác định bởi hai con trỏ L,R, trỏ đến phần tử trái và phải. Thuật toán sẽ chia bảng [L,R] thành ba bảng con: [L,U-1], [Ư1,V-1], [V+1,R]. Dựa vào giá trị khoá của Argument và giá trị khoá tại các điểm U=Step , V=L+2*Step. Tìm kiếm sẽ dừng nếu khoá của mẫu bằng với giá trị khoá của một trong hai điểm trên, ngược lại tìm kiếm sẽ tiếp tục trên một trong ba bảng con đơược chia. Quá trình cứ tiếp tục nhươ thế cho đến khi tìm đươợc phần tử mong muốn hoặc bảng phần tử đang sét là rỗng. Hình 1 mô tả hình thức tam phân của Trisearch theo sơ đồ “chia để trị”.

Thuật toán sau đây đơược trình bày đưới dạng giả mã, sẽ tìm kiếm phần tử Item trong mảng Key đã được sắp xếp theo thứ tự tăng dần:

 int Trisearch(int key[], int item, int l, int r)
{
 int u, v, result, step;
 result=0;
 while ((l<=r) && (result==0))
 {
     step =(r-l+1) / 3;
     u=l+step; v=l+2*step;
     if (item == key[u] ) result=u;
     else
     if (item == key[v] ) result=v;
     else
     if (item > key[v] ) l=v+1 ;
     else
     if (item > key[u] )
     {
     l=ư1;
     r=v-1;
     }
 else
     r=u-1;
 }
 return (result);
} 

Chúng ta có thể cài đặt thuật toán trên theo phương pháp đệ quy. Với vùng bộ nhớ Stack hạn chế, nên lưu ý khi kích thước bảng phần tử lớn ta nên truyền tham số Key theo kiểu tham chiếu (địa chỉ). Điều này giúp ta tránh được lỗi “Stack overflow error” do tràn vùng bộ nhớ ngăn xếp.

 
 int Trisearch_dq( int key[], int item,int l, int r)  {
 int u, v, step;
 if (l<=r)
 {
 step=(r-l+1) / 3;
 u=l+step; v=l+2*step;
 if (item == key[u]) return u;
     else
 if (item == key[v]) return v;
     else
 if (item > key[v] )
     return Trisearch_dq(key, item,v+1,r);
     else+
 if (item > key[u] )
     return Trisearch_dq(key, item,ư1,v-1);
     else
     return Trisearch_dq(key, item,l,u-1);
 }
 else /*khong thanh cong*/
 return 0;
 } 

Khi nói đến các thuật toán tìm kiếm, chúng ta sẽ cảm thấy quen thuộc hơn với thuật toán tìm kiếm nhị phân (Binsearch). Có lẽ bởi tính tự nhiên của phương pháp và dễ cài đặt của thuật toán. Binsearch có độ phức tạp thuật toán về thời gian là O(log2n). Vậy hiệu quả của Trisearch so với Binsearch? Dễ nhận thấy rằng so với Binsearch thì thuật toán Trisearch trong cài đặt đệ quy sẽ hội tụ nhanh hơn, hạn chế khả năng đệ quy sâu. Sau đây chúng ta sẽ phân tích độ phức tạp thuật toán về thời gian của Trisearch.
Không giảm tính tổng quát, ta giả thiết phạm vi tìm kiếm là từ 1 đến N, bảng key có N phần tử. Sau lần lặp thứ nhất phạm vi tìm kiếm là phần tử, sau lần lặp thứ 2 phạm vi tìm kiếm là N/3. Trong trường hợp tồi nhất vòng lặp While sẽ kết thúc khi N/3i =1, hay I = Log3n. Trong mỗi lần lặp tốn thời gian O(1) nên thời gian thực hiện của hàm Trisearch là O(log3n). Dễ nhận thấy rằng Binsearch và Trisearch có cùng độ phức tạp, hay O(log3n) = O(log2n) (vì log3n=log32 *log2n ). Nhìn vào bảng khảo sát liệt kê giá trị tại một số điểm (hình 2), đồ thị của Log3n, log32 (hình 3) ta cũng thấy được mối tương quan giữa hai hàm.

Nhưng có lẽ không nên đánh giá thuật toán tìm kiếm này tốt hơn thuật toán tìm kiếm khác. Điều quan trọng là sử dụng chúng sao cho phù hợp với từng ứng dụng và yêu cầu cụ thể. Không có cách nào hiểu thấu đáo một thuật toán nhanh hơn là bắt tay cài đặt chúng. Mình rất mong được học hỏi và đóng góp ý kiến của tất cả các bạn (Tanbv_it@yahoo.com).

[huynguyen]

int Trisearch_dq( int key[], int item,int l, int r)  {
 int u, v, step;
 if (l<=r)
 {
 step=(r-l+1) / 3;
 u=l+step; v=l+2*step;
 if (item == key[u]) return u;
     else
 if (item == key[v]) return v;
     else
 if (item > key[v] )
     return Trisearch_dq(key, item,v+1,r);
     else+
 if (item > key[u] )
     return Trisearch_dq(key, item,ư1,v-1);
     else
     return Trisearch_dq(key, item,l,u-1);
 }
 else /*khong thanh cong*/
 return 0;
 }

int Trisearch_dq( int key[], int item,int l, int r)  {
 int u, v, step;
 if (l<=r)
 {
 step=(r-l+1) / 3;
 u=l+step; v=l+2*step;
 if (item == key[u]) return u;
     else
 if (item == key[v]) return v;
     else
 if (item > key[v] )
     return Trisearch_dq(key, item,v+1,r);
     else+
 if (item > key[u] )
     return Trisearch_dq(key, item,ư1,v-1);
     else
     return Trisearch_dq(key, item,l,u-1);
 }
 else /*khong thanh cong*/
 return 0;
 }

Cho cái code to lên 1 tí để bà con coi cho rõ nào.

[thai1988]

nếu là như vậy ta hoàn toàn có thể chia làm bốn làm năm phần
đặc biệt hữu hiệu với dãy có n lớn
ta có các thuật toán foursearch,fivesearch,and tensearch....

[hd_kinh_can]

Không có foursearch, fivesearch... mà chỉ có tetrasearch,....
Về lý thuyết, tìm kiếm tam phân nhanh hơn nhị phân chút xíu, nhưng thực tế người ta ít dùng hơn, vì sao? Vì thời gian chậm hơn, có thể nói độ phức tạp thuật toán là như nhau, nhưng phép tìm kiếm tam phân phải dùng để 2 phép so sánh (mất thời gian đáng kể nhất là với so sánh string), còn nhị phân chỉ thực hiện một. Với giới hạn số phần tử cực kỳ lớn thì tìm kiếm tam phân mới tỏ ra hữu hiệu.