 |
| Chia để trị trong chiến tranh |
Thuật ngữ chia để trị áp dụng trong chiến tranh có ý nghĩa là đánh bại một vài nhóm đối thủ nhỏ hơn thì dễ hơn là đánh bại một nhóm lớn. Tương tự các thuật toán chia để trị tận dụng lợi thế của việc chia nhỏ vấn đề thành một hoặc nhiều bài toán con để giải chúng độc lập.
Các bước thực hiện giải thuật chia để trị.
- Bước 1: Chia bài toán thành các bài toán con không trùng lặp
- Bước 2: Giải bài toán con bằng đệ quy
- Bước 3: Kết hợp các kết quả
Ví dụ 1: Tìm kiếm tuyến tính
Tìm kiếm tuyến tính là một ví dụ tầm thường cho việc sử dụng giải thuật chia để trị để giải quyết bài toán này.
Ví dụ 2: Tìm kiếm nhị phân
Input: Một danh sách $A[low,...,high]$ đã được sắp xếp và một từ khóa $k$.
Output: Nếu $A[i]=k$ thì kết quả là $i$, nếu $A[i]<k$ thì kết quả là chỉ số $i$ lớn nhất để $A[i]<k$, nếu
$k<A[low]$ thì kết quả là $low-1.$
Code sử dụng đệ quy trong python:
def BinarySearch(A,low,high,key):
if high<low:
return low-1
mid=(low+high)//2
if A[mid]==key:
return mid
elif key<A[mid]:
return(BinarySearch(A,low,mid-1,key))
elif key>A[mid]:
return(BinarySearch(A,mid+1,high,key))Code sử dụng vòng lặp trong python.
def BinarySearch(A,low,high,key):
while low<=high:
mid=(low+high)//2
if A[mid]==key:
return mid
elif key<A[mid]:
high=mid-1
else:
low=mid+1
return low-1Thời gian chạy của thuật toán $T(n)=T \left(\left \lfloor \frac{n}{2} \right \rfloor \right) +C=T \left(\left \lfloor \frac{n}{2^2} \right \rfloor \right) +2C=T \left(\left \lfloor \frac{n}{2^k} \right \rfloor \right) +kC \leq T \left(\frac{n}{2^k} \right)+kC=T(1)+log_2(n).C$ $=T(0)+C+log_2(n).C=C+C+log_2(n).C=(log_2(n)+2).C \leq log_2(n).K$
Vậy $T(n)=O(log_2(n))$
Ví dụ 3: Bài toán phép nhân đa thức (thuật toán karatsuba)
Input: Cho 2 đa thức $A$ và $B$ có bậc là $n-1:$
$A(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_1x+a_0$
$B(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+...+b_1x+b_0$
Output: Tích hai đa thức $A.B$
$C(x)=c_{2n-2}x^{2n-2}+c_{2n-3}x^{2n-3}+...+c_1x+c_0$
Trong đó:
$c_{2n-2}=a_{n-1}.b{n-1}$
$c_{2n-3}=a_{n-1}.b_{n-2}+a_{n-2}.b_{n-1}$
$...$
$c_2=a_2.b_0+a_1.b_1+a_0.b_2$
$c_1=a_1.b_0+a_0.b_1$
$c_0=a_0.b_0$
Code Python:
def MultPoly(A,B,n):# n là độ lớn của danh sách A hoặc B
C=[0]*(2*n-1)
for i in range(len(A)):
for j in range(len(B)):
C[i+j]=C[i+j]+A[i]*B[j]
return CThời gian chạy của thuật toán là $O(n^2)$
Phân tích chia để trị(Karatsuba).
$A(x)=D_1(x)x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0(x)$ trong đó
$D_1(x)=a_{n-1}x^{n-1-\left \lfloor \frac{n}{2} \right \rfloor}+a_{n-2}x^{n-2-\left \lfloor \frac{n}{2} \right \rfloor}+...+a_{\left \lfloor \frac{n}{2} \right \rfloor}$
$D_0(x)=a_{\left \lfloor \frac{n}{2} \right \rfloor -1}x^{\left \lfloor \frac{n}{2} \right \rfloor -1}+a_{\left \lfloor \frac{n}{2} \right \rfloor -2}x^{\left \lfloor \frac{n}{2} \right \rfloor -2}+...+a_0$
$B(x)=E_1(x)x^{\left \lfloor \frac{n}{2} \right \rfloor}+E_0(x)$
$AB=(D_1x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0)(E_1x^{\left \lfloor \frac{n}{2} \right \rfloor}+E_0)=D_1E_1x^{2\left \lfloor \frac{n}{2} \right \rfloor}+(D_1E_0+D_0E_1)x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0E_0$
$=D_1E_1x^{2\left \lfloor \frac{n}{2} \right \rfloor}+\left [(D_1+D_0)(E_1+E_0)-D_1E_1-D_0E_0\right ]x^{\left \lfloor \frac{n}{2} \right \rfloor}+D_0E_0$
Tính $D_1E_1,(D_1+D_0)(E_1+E_0),D_0E_0$.
Thời gian chạy của thuật toán là $T(n)=3T(\frac{n}{2})+kn=3^2T(\frac{n}{2^2})+(1+\frac{3}{2})kn=...=3^iT(\frac{n}{2^i})+\sum_{i=0}^{i-1} \left (\frac{3}{2} \right )^i kn $
($kn$ là thời gian cộng hai dãy $D_1+D_0$ và $E_1+E_0$ )
Ta có $\sum_{i=0}^{i-1} \left ( \frac{3}{2} \right )^i =2n^{\log_{2}{3}-1}-2$ và $a^{\log_bc}=\left (b^{\log_ba} \right )^{\log_bc}=\left (b^{\log_bc} \right )^{\log_ba}=c^{log_ba}$
Quá trình kết thúc khi $2^i=n \Rightarrow i=log_2(n).$ Khi đó $T(n)=n^{log_23}T(1)+2kn^{\log_23}-2kn$
Vậy độ phức tạp của thuật toán là $T(n)=O(n^{log_2(3)})=O(n^{1.58})$
Code python
import numpy as np
def MultPoly(A, B):
n, m = len(A), len(B)
if n == 1:
return B*A[0]
if m == 1:
return A*B[0]
mid_n, mid_m = n//2, m//2
mid = min(mid_n, mid_m)
D1, D0, E1, E0 = A[:mid_n], A[mid_n:], B[:mid_m], B[mid_m:]
D1D0 = np.append(D1 + D0[:len(D1)], D0[len(D1):])
E1E0 = np.append(E1 + E0[:len(E1)], E0[len(E1):])
D1xE1 = MultPoly(D1, E1)
D0xE0 = MultPoly(D0, E0)
D1D0xE1E0 = MultPoly(D1D0, E1E0)
D1D0xE1E0 = np.append(D1D0xE1E0[:len(D1xE1)] - D1xE1, D1D0xE1E0[len(D1xE1):])
D1D0xE1E0 = np.append(D1D0xE1E0[:len(D0xE0)] - D0xE0, D1D0xE1E0[len(D0xE0):])
AxB = np.zeros(n + m - 1)
AxB[ : mid_n + mid_m -1] += D1xE1
AxB[mid_n + mid_m : n + m - 1] += D0xE0
AxB[mid : mid + len(D1D0xE1E0)] += D1D0xE1E0
return AxB
A = np.array([1,2,3,4])
B = np.array([4,3,2,1])
MultPoly(A,B)Chú ý : Nếu độ lớn của A và B không bằng nhau thì mình có ý tưởng không hay lắm như sau là chèn phần tử không vào phía trước mảng bé hơn sau khi được kết quả ta xóa đi phần tử không ở phía trước kết quả
Chúng ta thấy sử dụng giải thuật chia để trị để giải một bài toán thì phải sử dụng đệ quy. Như vậy khi đánh giá độ phức tạp của thuật toán chúng ta phải giải được hệ thức truy hồi mà đệ quy tạo ra. Việc này rất mất thời gian cho nên định lý Master ra đời.
Phát biểu định lý Master
Nếu $T(n)=aT \left (\left \lceil \frac{n}{b} \right \rceil \right)+O(n^d)(a >0,b>1,d \geq 0),$ thì:
$T(n)=\begin{cases} O(n^d)& \text{nếu } d> \log_{b}a \\ O(n^d \log_bn)& \text{nếu } d = \log_{b}a\\ O(n^{\log_ba})& \text{nếu } d < \log_{b}a \end{cases}$
Chứng minh định lý Master.
Không có nhận xét nào:
Đăng nhận xét