Chia để trị theo mình là một trong những phương pháp hiệu quả nhất để thiết kế thuật toán. Bài trước chúng ta đã làm quen với Quick Sort, Merge Sort và Linear Selection sử dụng chia để trị. Bài này khái quát hóa phương pháp và sau đó chúng ta xem xét các ví dụ áp dụng. Nguyên lí của chia để trị gồm hai bước như sau:

 
Cả hai bước đều yêu cầu những kĩ thuật nhất định và phương pháp tốt nhất để có thể áp dụng hai bước vào các bài toán khác nhau là thực hành nhiều. Trong bài này mình sẽ đưa ra các ví dụ minh họa hai bước, và đừng quên xem lại các phương pháp giải hệ thức truy hồi vì nó sẽ là công cụ chính để phân tích thời gian trong bài này.
Tính lũy thừa

 
Phương pháp mà bạn có thể nghĩ ngay tới là sử dụng công thức: $a^n = a\cdot a^{n-1}$. Ta có giả mã

 
Thời gian tính của SLOWPOWER là $O(n)$ (giả sử phép nhân được thực hiện trong thời gian $O(1)$). Tuy nhiên, ta có thể tính nhanh hơn $O(n)$ bằng cách áp dụng phương pháp chia để trị để giải bài toán nhanh hơn. Ở đây ta có nhận xét:

$a^n = a^{\lfloor n/2 \rfloor}\cdot a^{\lceil n/2 \rceil}$

Như vậy nếu ta biết $a^{\lfloor n/2 \rfloor}$ và $a^{\lceil n/2 \rceil}$ ta có thể tính $a^n$. Nhận thấy là tính $a^{\lfloor n/2 \rfloor}$ và $a^{\lceil n/2 \rceil}$ đều là các bài toán nhỏ hơn vì lũy thừa nhỏ hơn. Như vậy ta có:

 
Như vậy thời gian tính của thuật toán là:

 
Giải ra ta được $T(n) = O(\log n)$.

Nhân hai số nguyên $n$ bit

Trong phần này ta sẽ thảo luận bài toán sau:

Như ta đã biết bằng phương pháp đặt tính nhân của cấp 1, ta có thể nhân hai số nguyên $n$ bít bằng $O(n^2)$ phép cộng bit. Trong bài này, mình sẽ giới thiệu phương pháp nhân hai số $n$ bít trong thời gian $O(n^{\log_2 3})$

Trước khi đi vào thuật toán, mình giới thiệu câu đố nhân hai số phức của Gauss. Câu đố này sẽ cung cấp tư tưởng chính của thuật toán sẽ trình bày.

 
Lời giải là có, và cách làm như sau:

 
Tích của hai số phức chính là $X6,X_7$. Không khó để kiểm tra rằng chỉ mất 305 đồng để thực hiện các phép toán ở trên.

Trở lại với bài toán nhân số nguyên. Để đơn giảm ta giả sử $n = 2^k$. Hai số nguyên $X,Y$ có thể được viết lại như sau:

 
Trong đó $a,b,c,d$ là các số nguyên $n/2$ bit.

Như vậy ta có:

 
Như vậy để tính $XY$, ta có thể tính các tích $ac, ad, bd, bc, bd$ và sau đó thực hiện các phép dịch trái (nhân với $2^n$ tương đương với dịch trái $n$ bít) và cộng. Chú ý là các số $a,b,c,d$ có chiều dài $n/2$ bít, do đó mất thời gian $T(n/2)$ để thực hiện phép nhân. Như vậy ta có thể tính $XY$ trong thời gian:

 
Giải công thức truy hồi trên ta được $T(n) = O(n^2)$. Oops! Không nhanh hơn thuật toán nhân cấp 1.

Nếu để ý kĩ ta có thể thấy có sự tương đồng khi tính $XY$ và Gauss Puzzle. Sử dụng phương pháp như của Gauss (bài tập), ta có thể tính $ac, ad+bc, bd $ sử dụng 3 phép nhân hai số $n/2$ bít và vài phép cộng. Như vậy ta có thể tính $X.Y$ trong thời gian:

 
Giả mã của chương trình như sau:

 
Thuật toán nhanh nhất hiện tại để nhân hai số nguyên $n$ bít phát minh bới Martin Fürer với thời gian $O(n\log n 2^{\log^* n})$ trong đó hàm $\log^*n$ được định nghĩa như sau:
$\log^*(n) = \begin{cases} 1, & \mbox{if } n \leq 2 \\ 1 + \log^*(\log n) & \mbox{otherwise}\end{cases}$
Hàm $\log^* n$ tăng cực kì chậm. Với $n=2^{2^{16}} \simeq 2\cdot 10^{19728}$, $\log^*(n) = 5$. Do đó, trong thực tế ta có thể coi thuật toán Fürer có thời gian cỡ $O(n\log n)$. Tuy nhiên, về mặt lý thuyết, bài toán nhân hai số nguyên $n$ bít trong thời gian $O(n\log n)$ vẫn là một bài toán mở.

 
Tìm kiếm nhị phân

Tìm kiếm nhị phân (binary search) là một trong những thuật toán được sử dụng rộng rãi nhất trong thiết kế giải thuật. Bài toán như sau:

 
Nếu duyệt hết các phần tử của mảng từ đầu đến cuối, ta sẽ mất $O(n)$ để tìm. Tuy nhiên ta có thể lợi dụng tính chất mảng $A[1,2,\ldots,n]$ đã sắp xếp để thiết kế giải thuật tốt hơn:

Theorem: Tồn tại một thuật toán tìm ra một phần tử của mảng $A[1,2,\ldots,n]$ đã sắp xếp có giá trị $a$ trong thời gian $O(\log n)$.

 
Ở đây để đơn giản ta sẽ giả sử mảng $A$ có ít nhất một phần tử có gía trị $a$. Ý tưởng của tìm kiếm nhị phân khá đơn giản: so sánh $a$ với phần tử $A[n/2]$. Nếu $a$ < $A[n/2]$, ta tìm kiếm trên $A[1,2,\ldots, n/2-1]$. Nếu $a$ > $ A[n/2]$, ta tìm kiếm trên $A[n/2+1,\ldots, n]$. Giả mã như sau:

 
Code của giả mã bằng C. Code đầy đủ của thuật toán được đính ở cuối bài.

// x, y is the first and last index of array _array
int binary_search(int _array[], int x, int y, int a){
if(x == y) return x;
else if( x< y){
int m = (x+y)/2;
if(_array[m] < a) {
return binary_search(_array, m+1, y, a);
}else if(_array[m] > a){
return binary_search(_array, x, m-1, a);
} else {
return m;
}
}
return -1;
}

 
Ta thấy ở mỗi bước tìm kiếm, chúng ta loại bỏ được ít nhất một nửa số phần tử cuả mảng. Như vậy:

Code: binary search

Tham khảo
 
[1] Jeff Erickson. Algorithm Lecture Notes, UIUC.
[2] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. 1st Edition). McGraw-Hill Higher Education, (2008).
[3] Anupam Gupta and John Lefferty. Great Theoretical Ideas in Computer Science Lecture Notes, CMU, 2008.

Bài Tập
 
Bài tập trong phần này được trích từ chapter 2 của cuốn sách Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.
 
Bài 1 Giả sử ta có một mảng gồm $n$ phần tử và các phần tử có thể trùng nhau. Thiết kế giải thuật loại bỏ tất cả các phần từ trùng nhau (giữ lại một copy) trong thời gian $O(n\log n)$.
 
Bài 2 Giả sử trong bộ nhớ máy tính có một mảng vô hạn các phần tử $A[1,2,3,\ldots, \infty]$ trong đó $n$ phần tử đầu tiên được xắp xếp theo chiều tăng dần và còn lại là $\infty$. Tuy nhiên, bạn không biết $n$, nghĩa là bạn không biết trong mảng có bao nhiêu phần tử khác $\infty$. Mỗi lần bạn truy cập vào một vị trí lớn hơn $n$ thì máy tính sẽ trả lại $\infty$. Bây giờ bạn có một số nguyên $x$ và muốn tìm vị trí cuả mảng chứa gía trị $x$. Hãy thiết kế giải thuật tìm vị trí của $x$ trong mảng với thời gian $O(\log n)$.
 
Bài 3 Bạn có một mảng $A[1,2,3,\ldots, n]$ gồm các số nguyên đôi một khác nhau đã săp xếp theo thứ tự tăng dần và bạn muốn tìm chỉ số $i$ của mảng sao cho $A[i]= i$. Hãy thiết kế thuật toán với thời gian $O(\log n)$.

 
Bài 4 (Closest Pair) Cho một tập $n$ điểm trên một mặt phẳng $p_1 = (x_1,y_1),p_2 = (x_2,y_2), \ldots, p_n = (x_n,y_n)$. Xác định cặp điểm gần nhất, đó là cặp điểm $p_i\not=p_j$ sao cho khoảng cách giữa $p_i,p_j$ là nhỏ nhất. Khoảng cách đó được tính bởi công thức $\sqrt{(x_i-x_j)^2 + (y_i - y_j)^2}$. Để đơn giản ở đây giả sử $n = 2^k$, tất cả các tọa độ trên trục $x$ đôi một khác nhau và tất cả các tọa độ trên trục $y$ đôi một khác nhau. Ý tưởng cơ bản như sau:

• Tìm giá trị $x$ sao cho một nửa số điểm có tọa độ $x_i < x$ và nửa còn lại có tọa độ $x_i > x$. Gọi hai nửa đó là $L, R$.
• Đệ quy để tìm cặp điểm gần nhất của $L$ và $R$. Gọi 2 cặp điểm đó là $p_L,q_L \in L$ và $p_R,q_R \in R$ với khoảng cách lần lượt là $d_L,d_R$. Gọi $d = \min (d_L,d_R)$.
• Bây giờ ta cần tìm một điểm trong $L$ và một điểm trong $R$ sao cho khoảng cách giữa hai điểm đó nhỏ hơn $d$. Ta có thể loại bỏ đi những điểm có $x_i < x-d$ và $x_i > x+d$ và sắp xếp những điểm còn lại theo chiều tăng của tọa độ $y$.
• Bây giờ duyệt danh sách đã sắp xếp, với mỗi điểm, tính khoảng cách giữa nó và 7 điểm sau nó trong danh sách đã sắp xếp. Gọi $p_M,q_M$ là hai cặp điểm gần nhất tìm được
• Đáp số là căp điểm gần nhất giữa ba cặp điểm $\{p_L,q_L\},\{p_R,q_R\},\{p_M,q_M\}$

Câu hỏi như sau:

1. Chứng minh thuật toán ở trên là đúng dựa trên tính chất sau: bất kì hình vuông nào có kích thước $d\times d$ trong mặt phẳng chứa tối đa $4$ điểm của $L$
2. Viết giả mã cho thuật toán trên và chứng minh rằng thời gian tính của thuật toán được cho bởi công thức sau:

   $ T(n) = 2T(\frac{n}{2}) + O(n\log n)$

   Chứng minh rằng thời gian chạy là $T(n) = O(n\log^2 n)$.

3. Liệu bạn có thể thiết kế giải thuật với thời gian $O(n\log n)$ không?