Chọn phần tử lớn thứ k của mảng--Median Selection

Trong bài này chúng ta giải bài toán sau:

Problem (k-th selection): Cho mảng $A[1,2,\ldots, n]$ gồm $n$ phần tử. Tìm phần tử lớn thứ $k$ của mảng.

 
Có hai cách giải mà chúng ta có thể nghĩ đến ngay:

  1. Dựa vào định nghĩa: phần tử thứ $k$ lớn hơn (hoặc bằng) $k-1$ phần tử của mảng và nhỏ hơn (hoặc bằng) $n-k$ phần tử khác. Như vậy ta có thể giải với thời gian $O(n^2)$ bằng cách với mỗi phần tử, kiểm tra tính chất trên trong thời gian $O(n)$.
  2. Sắp xếp mảng theo chiều tăng dần và lấy ra phần tử thứ $k$ của mảng đã sắp xếp. Sắp xếp có thể thực hiện trong thời gian $O(n\log n)$. Như vậy bài toán trên có thể giải trong thời gian $O(n\log n)$.

Bài này giới thiệu phương pháp chia để trị để giải bài toán trên trong thời gian $O(n)$.

Lemma: Tồn tại thuật toán chọn ra phần tử lớn thứ $k$ của mảng $A[1,2,\ldots, n]$ trong thời gian $T(n) = O(n)$.

 

Ý tưởng cơ bản

Ý tưởng cơ bản của thuật toán như sau: Chọn một phần tử (bất kì), $A[p]$, và chia mảng ra thành hai phần (trong thời gian $O(n)$): phần 1 gồm những phần tử nhỏ hơn $A[p]$ và phần 2 gồm những phần tử lớn hơn (hoặc bằng) $A[p]$. Ta có hai trường hợp:

  1. Nếu $k$ nhỏ hơn kích thước của phần 1, chúng ta đệ quy trên phần 1 để tìm phần tử thứ $k$.
  2. Nếu $k$ lớn hơn kích thước của phần 1, chúng ta đệ quy trên phần 2 tìm phần tử thứ $r-k$, ở đây $r$ là kích thước của phần 1.

 
Giả mã của thuật toán chia mảng với phân tử chọn (pivot) là $A[p]$, trả lại vị trí mới cuả phần tử có giá trị $A[p]$ trong mảng.

Partition($A[1,2,\ldots, n],p$):
    swap $A[p] \leftrightarrow A[n]$
    $i \leftarrow 0$
    $i \leftarrow n$
    while $i$ < $j$
       repeat $i \leftarrow i + 1$ until $(i \geq i \mbox{ or } A[i]\geq A[n])$
       repeat $i \leftarrow j - 1$ until $(i \geq i \mbox{ or } A[j]\geq A[n])$
       if $i$ < $j$
          swap $A[i] \leftrightarrow A[j]$
    swap $A[i] \leftrightarrow A[n]$
    return $i$

 
Dưới đây là code C của giả mã trên.

// x, y is the first and last index of array arr
// p is the index of the pivot, x &lt;= p &lt;= y
int partition(int arr[], int x, int y, int p){
swap(&amp;arr[p],&amp;arr[y]);
int i = x;
int j = y-1;
while( i &lt;= j){
while(arr[i] &lt; arr[y] &amp;&amp; i &lt;= j){i++;}
while(arr[j] &gt;= arr[y] &amp;&amp; i &lt;= j){j--;}
if(i &lt; j) swap(&amp;arr[i],&amp;arr[j]);
}
swap(&amp;arr[i],&amp;arr[y]);
return i;
}

Như vậy ta đã thực hiện xong bước một: phân chia mảng bằng phần tử bất kì. Sau đây là giả mã thực hiện bước đệ quy:

QickSelect($A[1,2,\ldots, n],k$):
    if $n ==1$
       return $A[1]$
    else
       Choose a pivot $A[p]$
       $r \leftarrow$ Partition$(A[1,2,\ldots, n],p)$
       if $k$ < $ r$
           return QuickSelect$(A[1,2,\ldots, r-1],k)$
       else if $k$ > $r$
           return QuickSelect$(A[r+1,2,\ldots, n],k-r)$
       else
           return $A[r]$

 
Dưới đây là code C của giả mã trên. Code đầy đủ với phần tử pivot là phần tử giữa của mảng được cho ở cuối bài viết.

// x, y is the first and last index of array arr
// k is the index of the choosen element
int quick_select(int arr[], int x, int y, int k){
if(y &lt;= x) return arr[x];
else {
int p = (y+x)/2; // choose the mid element to be the pivot
int r = partition(arr, x, y, p);
if ( k &lt; r){
return quick_select(arr, x, r-1, k);
}else if (k &gt; r) {
return quick_select(arr, r+1, y, k);
}else {
return arr[r];
}
}
}
}

Chọn pivot tốt

Nhìn vào giả mã ta dễ thấy thời gian chạy trong trường hợp tồi nhất như sau:

\begin{array}{rcr} T(n) &=& \max_{1\leq r \leq n}(\max(T(r-1),T(n-r)) + O(n)) \\ &=&  \max_{0 \leq \ell \leq n-1} T(\ell) + O(n)\end{array}

 
Trường hợp xấu nhất khi $\ell = n-1$, khi đó $T(n) = O(n^2)$, không tốt hơn thuật toán vét cạn. Tuy nhiên, nếu ta chọn pivot sao cho $\ell \leq \alpha n$ với $\alpha < 1$, ta sẽ có

$ T(n) \leq T(\alpha n) + O(n)$

 
Giải công thức truy hồi trên ta được $T(n) = O(n)$. Trong những trường hợp không biết chọn phần tử nào là pivot tốt, cách đầu tiên có thể nghĩ tời là chọn ngẫu nhiên một phần tử của mảng làm pivot với xác suất như nhau. Với bài toán này, chọn ngẫu nhiên sẽ cho ta thuật toán với thời gian kì vọng (expected) là $O(n)$. Chi tiết phân tích bạn đọc có thể xem tại đây.

Blum, Floyd, Pratt, Rivest và Tarjan [2] đề xuất một cách khác để chọn pivot như sau: nếu số phần tử của mảng là lớn ($\geq 25$ trong giả mã), ta chia mảng thành $\lceil n/5 \rceil$ nhóm, mỗi nhóm gồm 5 phần tử. Dùng thuật toán vét cạn để tìm median của mỗi nhóm. Sau bước đó, ta thu được mảng gồm $\lceil n/5 \rceil$ phần tử là median của $\lceil n/5 \rceil$ nhóm. Gọi đệ quy để tìm median của mảng này. Lấy median làm pivot cho mảng ban đầu. Giả mã như sau:

LinearSelection($A[1,2,\ldots, n],k$):
    if $n \leq 25$
       use brute force
    else
       $m \leftarrow \lceil n/5 \rceil$
       for $i \leftarrow 1$ to $m$ do
          $M[i] \leftarrow$ MedianOfFive$(A[5i-4,\ldots, 5i])$
       $A[p] \leftarrow $ LinearSelection$(M[1,2, \ldots, m], \lfloor m/2 \rfloor)$
       $r \leftarrow $ Partition$(A[1,2, \ldots, p], \lfloor m/2 \rfloor)$
       if $k$ < $ r$
           return LinearSelection$(A[1,2,\ldots, r-1],k)$
       else if $k$ > $ r$
           return LinearSelection$(A[r+1,2,\ldots, n],k-r)$
       else
           return $A[r]$

 
Dưới đây là code C của giả mã trên. Code đầy đủ được cho ở cuối bài viết.

int linear_selection(int _array[], int x, int y, int k){
if(y - x &lt;= 24) {
return med_exhaustive(_array, x, y ,k);//brute force search
} else {
int m = (y-x+1)/5 + ((y-x+1)%5 &gt; 0? 1 : 0); // m = ceiling(n/5)
int _brray[m];
int i = 0;
for (i = 0 ; i &lt; m-1 ; i++){
_brray[i] = med_of_five(_array[5*i+x], _array[5*i+1+x],_array[5*i+2+x], _array[5*i+3+x], _array[5*i+4+x]);
}
_brray[m-1] = _array[y];
int med_of_brray = linear_selection(_brray, 0, m-1, m/2-1); // find median of of medians
int p  =  0;
for( i = x ; i &lt;= y  ; i++){
if (_array[i] == med_of_brray) p = i;
}
int r = partition(_array, x, y, p);
if ( k &lt; r){
return linear_selection(_array, x, r-1, k);
}else if (k &gt; r) {
return linear_selection(_array, r+1, y, k);
}else {
return _array[r];
}
}
}

Phân tích thời gian
Ta thấy tìm median của medians mất thời gian $T(n/5)$. Vì phần tử pivot là median của median, mỗi bước đệ quy ta sẽ bỏ bớt được ít nhất là $3n/10$ phần tử (tại sao?). Như vậy tổng thời gian của thuật toán là:

$T(n) = T(n/5) + T(7n/10) + O(n)$

 
Giải công thức đệ quy trên, ta được $T(n) = O(n)$.

Dưới đây là code và dữ liệu test: Code, Data

Tham khảo
Bài viết dự chủ yêu trên notes của Jeff Erickson
http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/01-recursion.pdf

Tài liệu tham khảo liên quan:
[1] Avrim Blum: Algorithm Lecture Notes , CMU, 2011.
[2] M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time Bounds for Selection. Journal of Computer and System Sciences, 7(4), 448-461. 1973.
Facebook Comments

Tags: , ,

Reply

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