Chia Để Trị I
Bài 5: Chia để trị
Chia để trị là một trong những phương pháp hiệu quả nhất để thiết kế thuật toán. Trong bài này ta sẽ tìm hiểu nguyên lý và một số ví dụ minh hoạ cơ bản. Trong bài tiếp theo ta sẽ áp dụng phương pháp này cho các bài toán phức tạp hơn.
- Bước 1 (chia): Chia bài toán lớn thành các bài toán con nhỏ hơn
- Bước 2 (trị): Gọi đệ quy giải các bài toán con, sau đó gộp lời giải của bài toán con thành lời giải bài toán lớn.
Ta sẽ tìm hiểu các áp dụng nguyên lý này thông qua các ví dụ.
Ghi chú 1: Trong bài này ta sẽ phải giải nhiều hệ thưucs truy hồi. Bạn nên xem lại kiến thức cơ bản tại đây.
1. 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}$. Giả mã tính như sau:
$x \leftarrow a$
for $i \leftarrow 2$ to $n$
$x \leftarrow x\cdot a$
return $x$
Do ta chỉ đơn giản thực hiện $n$ phép nhân, 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, áp dụng phương pháp chia để trị, ta có thể tính luỹ thừa nhanh hơn dựa trên nhận xét sau:
$a^n = a^{\lfloor n/2 \rfloor}\cdot a^{\lceil n/2 \rceil}$
Do 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, ta có thể áp dụng chia để trị. Giả mã như sau:
if $n=1$
return $a$
else
$x\leftarrow $ FASTPOWER($a, \lfloor n/2 \rfloor$)
if $n$ is even
return $x\cdot x$
else $n$
return $x\cdot x\cdot a$
Gọi $T(n)$ là số phép nhân thực hiện để tính $a^n$. Ta có công thức đệ quy sau:
$T(n) \leq T(\lfloor n/2 \rfloor) + 2$
Giải ra ta được $T(n) = O(\log n)$.
Như vậy, số phép nhân đã giảm từ $n$ xuống còn $O(\log n)$ nếu ta dùng phương pháp chia để trị.
2. Nhân hai số nguyên $n$ bit
Xét bài toán sau:
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. Áp dụng chia để trị, ta có thể thực hiện 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, ta đi lạc đề một chút để tìm hiể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.
Ghi chú 2: Bạn nên thử suy nghĩ trước khi đọc lời giải dưới đây.
Lời giải:
\begin{array}{lll} X_1 & = & a + b \\ X_2 & = & c+d \\ X_3 & = & X_1X_2 = ac+ad + bc + bd \\ X_4 & = & ac \\ X_5 & = & bd \\ X_6 & = & X_4-X_5 = ac - bd \\ X_7 & = & X_3 - X_4 - X_5 = bc+ad \end{array}
Tính tích của hai số phức thực chất là tính $X_6$ và $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:
\begin{array}{lll} X & = & a2^{n/2} + b \\ Y & = & c2^{n/2}+d \end{array}
Trong đó $a,b,c,d$ là các số nguyên $n/2$ bit.
Ta suy ra:
$XY = (a2^{n/2} + b)(c2^{n/2}+d) = ac2^n + (ad+bc)2^{n/2} + bd $
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. Các phép toán này chỉ mất thời gian $O(n)$. Do các số $a,b,c,d$ có chiều dài $n/2$ bít, nếu gọi đệ quy, ta sẽ trả thời gian $4T(n/2)$ để thực hiện 4 phép nhân $ac, ad, bc, bd$ – ở đây $T(n)$ là thời gian để nhân hai số $n$ bít. Giải phương trình đệ quy:
$T(n) = 4T(n/2) + O(n)$
ta được $T(n) = O(n^2)$. Vậy là ta vẫn chưa thực hiện hanh hơn thuật toán nhân cấp 1!!!!!
Tuy nhiên, nếu để ý kĩ ta có thể thấy có sự tương đồng khi tính $XY$ và câu đố của Gauss. Sử dụng phương pháp như của Gauss, 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:
$T(n) = 3T(n/2) + O(n)$
Giải ra ta được $T(n) = O(n^{\log_2 3})$ như đã phát biểu trong định lý 1.
Giả mã của chương trình như sau:
if $n=1$
return $x\cdot y$
else
$m \leftarrow n/2$
$a \leftarrow \lfloor x/2^m \rfloor$; $b \leftarrow x \mod 2^m$
$c \leftarrow \lfloor y/2^m \rfloor$; $d \leftarrow y \mod 2^m$
$e\leftarrow $ FASTMULT($a,c, m$)
$f\leftarrow $ FASTMULT($b,d, m$)
$g\leftarrow $ FASTMULT($a - b,c -d, m$)
return $2^{n}e + 2^m(e+f-g) + f$
Ngoài lề: 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)$ là một hàm 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)$. Gần đây, hai nhà nghiên cứu David Harvey và Joris van der Hoeven đã đăng lên một công trình nhân hai số nguyên $n$ bít trong thời gian $O(n\log n)$.
3. Tìm kiếm nhị phân
Tìm kiếm nhị phân 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ìm kiếm với thời gian chỉ $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:
if $n=1$
return $n$
else
$m \leftarrow \lfloor n/2 \rfloor$
if $a$ < $A[m]$
return BinarySearch($A[1,2,\ldots,m-1],a$)
else if $a$ > $A[m]$
return BinarySearch($A[m+1,2,\ldots,n],a$)
else
return $m$
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 thời gian tìm kiếm $T(n)$ thoả mãn:
$T(n) = T(n/2) + O(1) = O(\log n)$
4. 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.
5. 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: (Bài toán cặp điểm gần nhất) 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:
- 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$
- 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)$. - Liệu bạn có thể thiết kế giải thuật với thời gian $O(n\log n)$ không?