Thuật toán chia để trị

     

Nơi tổng phù hợp và chia sẻ những kỹ năng và kiến thức liên quan lại tới giải mã nói bình thường và kim chỉ nan khoa học máy vi tính nói riêng.

Bạn đang xem: Thuật toán chia để trị


Chia để trị theo mình là một trong những phương thức hiệu quả tuyệt nhất để kiến tạo thuật toán. Bài trước họ đã làm cho quen cùng với Quick Sort, Merge Sort cùng Linear Selection thực hiện 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ị có hai cách như sau:


Divide & Conquer Principle: Bước 1 (divide): Chia vấn đề lớn thành các bài toán con nhỏ hơn Bước 2 (conquer): gọi đệ quy giải các bài toán con, sau đó dựa trên giải mã của việc con nhằm giải việc lớn.

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


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)$). Mặc dù nhiên, ta rất có thể tính nhanh hơn $O(n)$ bằng phương pháp áp dụng cách thức chia nhằm trị để giải vấn đề nhanh hơn. Ở trên đây ta tất cả nhận xét:

$a^n = a^lfloor n/2 floorcdot a^lceil n/2 ceil$

Như vậy nếu như ta biết $a^lfloor n/2 floor$ với $a^lceil n/2 ceil$ ta có thể tính $a^n$. Nhận ra là tính $a^lfloor n/2 floor$ cùng $a^lceil n/2 ceil$ gần như là các bài toán nhỏ dại hơn bởi lũy thừa nhỏ dại hơn. Bởi vậy ta có:


FASTPOWER($a,n$): if
$n=1$ return $a$ else $xleftarrow $ FASTPOWER($a, lfloor n/2 floor$) if $n$ is even return $xcdot x$ else $n$ return $xcdot xcdot a$

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


$T(n) leq T(lfloor n/2 floor) + 2$


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ẽ bàn bạc bài toán sau:


Problem 2:
đến hai số nguyên $X,Y$, từng số bao gồm độ lâu năm $n$ bít. Tính tích $XY$.

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


Theorem: mãi sau một thuật toán nhân nhì số nguyên $n$ che $X,Y$ trong thời gian $O(n^log_2 3) = O(n^1.585...)$

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


Gauss Puzzle: các bạn có hai số phức $a + bi, c+di$ và bạn cần tính $(a+bi)(c+di) = (ac-bd) + (ad+bc)i$ . Trả sử rằng để tiến hành phép nhân, các bạn phải trả 100 đồng và để triển khai một phép cùng hoặc một phép trừ chúng ta phải trả 1 đồng. Do vậy nếu tiến hành nhân số phức bằng cách tính tích $ac, bd, ad, bc$, một phép cùng và một phép trừ, chúng ta phải trả 402 đồng. Câu hỏi là bạn có thể thực hiện tại nhân số phức với thấp hơn 402 đồng không?

Lời giải là có, và biện pháp làm như sau:


eginarraylll X_1 và = và a + b \ X_2 & = và c+d \ X_3 và = & X_1X_2 = ac+ad + bc + bd \ X_4 và = và ac \ X_5 và = & bd \ X_6 và = và X_4-X_5 = ac - bd \ X_7 và = & X_3 - X_4 - X_5 = bc+ad endarray


Tích của hai số phức đó là $X6,X_7$. Không nặng nề để khám nghiệm rằng chỉ mất 305 đồng để tiến hành các phép toán sống trên.

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


eginarraylll X và = & a2^n/2 + b \ Y & = & c2^n/2+d endarray


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

*
Như vậy ta có:


$XY = (a2^n/2 + b)(c2^n/2+d) = ac2^n + (ad+bc)2^n/2 + bd $


Như vậy để tính $XY$, ta hoàn toàn có thể tính các tích $ac, ad, bd, bc, bd$ và tiếp đến thực hiện những phép dịch trái (nhân cùng với $2^n$ tương tự với dịch trái $n$ bít) và cộng. để ý là những số $a,b,c,d$ bao gồm chiều nhiều năm $n/2$ bít, vì thế mất thời gian $T(n/2)$ để thực hiện phép nhân. Vì vậy ta hoàn toàn có thể tính $XY$ vào thời gian:


$T(n) = 4T(n/2) + O(n)$


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

Nếu lưu ý kĩ ta hoàn toàn có thể thấy gồm sự tương đương khi tính $XY$ với 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 nhị số $n/2$ bít và vài phép cộng. Bởi thế ta hoàn toàn có thể tính $X.Y$ trong thời gian:


$T(n) = 3T(n/2) + O(n) = O(n^log_2 3)$


Giả mã của lịch trình như sau:


FASTMULT($x,y,n$): if
$n=1$ return $xcdot y$ else $m leftarrow n/2$ $a leftarrow lfloor x/2^m floor$; $b leftarrow x mod 2^m$ $c leftarrow lfloor y/2^m floor$; $d leftarrow y mod 2^m$ $eleftarrow $ FASTMULT($a,c, m$) $fleftarrow $ FASTMULT($b,d, m$) $gleftarrow $ FASTMULT($a - b,c -d, m$) return $2^ne + 2^m(e+f-g) + f$

Thuật toán nhanh nhất có thể hiện tại nhằm nhân hai số nguyên $n$ bít phát minh sáng tạo bới Martin Fürer với thời gian $O(nlog n 2^log^* n)$ trong các số đó hàm $log^*n$ được có mang như sau:$log^*(n) = egincases 1, và mboxif n leq 2 \ 1 + log^*(log n) và mboxotherwiseendcases$Hàm $log^* n$ tăng rất là chậm. Với $n=2^2^16 simeq 2cdot 10^19728$, $log^*(n) = 5$. Bởi vì đó, trong thực tiễn ta rất có thể coi thuật toán Fürer có thời hạn cỡ $O(nlog n)$. Mặc dù nhiên, về khía cạnh lý thuyết, bài toán nhân hai số nguyên $n$ bít trong thời gian $O(nlog n)$ vẫn là một trong những bài toán mở.

Xem thêm: Điểm Chuẩn Học Viện Kỹ Thuật Mật Mã Điểm Chuẩn 2020, Điểm Chuẩn Học Viện Kỹ Thuật Mật Mã

kiếm tìm kiếm nhị phân

Tìm kiếm nhị phân (binary search) là trong những thuật toán được sử dụng thoáng rộng nhất trong kiến tạo giải thuật. Câu hỏi như sau:


Problem 3:
cho một mảng $A<1,2,ldots,n>$ đã thu xếp theo chiều tăng nhiều và một vài nguyên $a$. Tìm địa chỉ của $a$ vào mảng.

Nếu chú ý hết các bộ phận của mảng từ đầu đến cuối, ta vẫn mất $O(n)$ để tìm. Tuy nhiên ta rất có thể lợi dụng đặc điểm mảng $A<1,2,ldots,n>$ đã thu xếp để kiến tạo giải thuật xuất sắc hơn:

Theorem: lâu dài một thuật toán tra cứu ra 1 phần tử của mảng $A<1,2,ldots,n>$ đã bố trí có giá trị $a$ trong thời hạn $O(log n)$.

Ở đây để đơn giản ta vẫn giả sử mảng $A$ gồm ít nhất một trong những phần tử có gía trị $a$. Ý tưởng của tìm kiếm nhị phân khá solo giản: so sánh $a$ với phần tử $A$. Nếu $a$ $ A$, ta kiếm tìm kiếm bên trên $A$. đưa mã như sau:


BinarySearch($A<1,2,ldots,n>,a$): if
$n=1$ return $n$ else $m leftarrow lfloor n/2 floor$ if $a$ BinarySearch($A<1,2,ldots,m-1>,a$) else if $a$ > $A$ return BinarySearch($A,a$) else return $m$

Code của giả mã bằng C. Code vừa đủ của thuật toán được gắn ở cuối bài.

// x, y is the first and last index of array _arrayint binary_search(int _array<>, int x, int y, int a)if(x == y) return x;else if( x 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 quăng quật được ít nhất một nửa số bộ phận cuả mảng. Như vậy:


$T(n) = T(n/2) + O(1) = O(log n)$


Code: binary search

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

bài xích Tập Bài tập vào 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 bao gồm $n$ bộ phận và các bộ phận có thể trùng nhau. Kiến thiết giải thuật thải trừ tất cả các phần từ bỏ trùng nhau (giữ lại một copy) trong thời hạn $O(nlog n)$.Bài 2 giả sử trong bộ lưu trữ máy tính có một mảng vô hạn các thành phần $A<1,2,3,ldots, infty>$ trong các số ấy $n$ bộ phận đầu tiên được xắp xếp theo chiều tăng ngày một nhiều và còn lại là $infty$. Tuy nhiên, bạn đắn đo $n$, nghĩa là bạn chần chừ 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í to hơn $n$ thì máy vi tính sẽ trả lại $infty$. Hiện giờ bạn có một số nguyên $x$ và ước ao tìm địa điểm cuả mảng cất gía trị $x$. Hãy thi công giải thuật tìm địa điểm của $x$ trong mảng với thời gian $O(log n)$.

Xem thêm: Cách Xin Giấy Đi Đường Đà Nẵng Cấp Giấy Đi Đường Mã Qr Trực Tuyến Như Thế Nào?

Bài 3 các bạn có một mảng $A<1,2,3,ldots, n>$ gồm các số nguyên song một không giống nhau đã săp xếp theo sản phẩm tự tăng cao và bạn muốn tìm chỉ số $i$ của mảng thế nào cho $A= i$. Hãy xây đắp thuật toán với thời gian $O(log n)$.

Bài 4 (Closest Pair) cho 1 tập $n$ điểm trên một khía cạnh phẳng $p_1 = (x_1,y_1),p_2 = (x_2,y_2), ldots, p_n = (x_n,y_n)$. Xác minh cặp điểm ngay sát nhất, sẽ là cặp điểm $p_i ot=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 bí quyết $sqrt(x_i-x_j)^2 + (y_i - y_j)^2$. Để dễ dàng ở đây giả sử $n = 2^k$, tất cả các tọa độ bên 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 dạng như sau:

Tìm giá trị $x$ sao để cho một nửa số điểm có tọa độ $x_i x$. điện thoại tư vấn hai nửa chính là $L, R$. Đệ quy để tìm cặp điểm gần nhất của $L$ với $R$. Hotline 2 cặp điểm này 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$. điện thoại tư vấn $d = min (d_L,d_R)$.Bây tiếng ta nên tìm một điểm trong $L$ và một điểm trong $R$ sao cho khoảng cách giữa nhì điểm đó nhỏ hơn $d$. Ta có thể loại loại bỏ những điểm có $x_i x+d$ và sắp xếp những điểm sót lại theo chiều tăng của tọa độ $y$.Bây giờ đồng hồ duyệt danh sách đã chuẩn bị xếp, với mỗi điểm, tính khoảng cách giữa nó và 7 điểm sau nó trong list đã sắp xếp. Call $p_M,q_M$ là hai cặp điểm sớm nhất tìm đượcĐáp số là căp điểm sớm nhất giữa tía 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 sinh hoạt 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 imes d$ trong mặt phẳng chứa về tối đa $4$ điểm của $L$Viết đưa mã mang đến 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(fracn2) + O(nlog n)$

Chứng minh rằng thời hạn chạy là $T(n) = O(nlog^2 n)$.Liệu bạn có thể thiết kế giải mã với thời gian $O(nlog n)$ không?