1.4- 1
Giả sử ta đang so sánh các cách thực thi phương pháp sắp xếp chèn
và sắp xếp trộn trên cùng một máy. Với các đdu vào có kích cỡn> tiến trình sắp xếp chèn chạy trong 8n2 bước, trong khi tiến trình sắp xếp trộn chạy trong 64nìg n bước. Với các giá trịn nào, phương pháp sắp xếp chèn sẽ đánh bại phương pháp sắp xếp trộn? Làm sao viết lại mã giả sắp xếp trộn để nó thậm chí chạy nhanh hơn trên các đầu vào nhỏ?
1.4- 2
Nêu giá trịn nhỏ nhất sao cho một thuật toán có thời gian thực hiện ỉà IQOn2 chạy nhanh hơn một thuật toán có thời gian thực hiện là 2n trên cùng một máy?
Các bài toán
1- 1 So sánh cấc thời gian thực hiện
Với mỗi hàm / (n) và thời gian t ưong bảng dưới đây, hãy xác định kích cỡn lớn nhất của một bài toán mà ta có thể giải trong thời gian giả định thuật toán để giải quyết bài toán bỏ ra/00 microgiây.?
1- 2 Sắp xếp chen trên các mảng nhỏ trong sắp xếp trộn
Mặc dù phương pháp sắp xếp trộn chạy trong Q(n lg n) thời gian trường hợp xấu nhất và sắp xếp chèn chạy trong 0(n2) thời gian trường hợp xấu nhất, các thừa số bất biến trong sắp xếp chèn khiến nó chạy nhanh hơn với n nhỏ. Do đó, tốt nhất ta nên sử dụng kỹ thuật sắp xếp chèn bên trong sắp xếp trộn khi các bài toán con trở nên đủ nhỏ. Xem xét một dạng cải biên kỹ thuật sắp xếp trộn ở đó n/k danh sách con có chiều dài k được sắp xếp bằng kỹ thuật sấp xếp chèn rồi được hợp nhất bằng cơ chế trộn chuẩn, ở đó Ả: là một giá trị sẽ được xác định.
a. Chứng tỏrứk danh sách con, mỗi danh sách có chiều dài kỷ có thể được sắp xếp bằng phương pháp sắp xếp chèn trong 0(n/c) thời gian trường hỢp-xấu nhất.
b. Chứng tỏ các danh sách con có thể được trộn trong 0(n lg(n/k)) thời gian ca xấu nhất.
c. Cho thuật toán đã sửa đổi chạy trong 0 (nk + n lg(n/k)) thời gian ca xấu nhất, nêu giá trị tiệm cận lớn nhất của k (hệ ký hiệu 0) dưới dạng một hàm n mà thuật toán đã sửa đổi có cùng thời gian thực hiện tiệm cận dưới dạng sắp xếp trộn chuẩn?
d. k được chọn ra sao trong thực tế?
1- 3 Các phép nghịch đảo
ChoA[l..n] là một mảng n con số riêng biệt. Nếu i < j và A[ĩ\ > A[j]t thì cặp (í, j) được gọi là một phép nghịch đảo[inversion] của A.
a. Liệt kê năm phép nghịch đảo của mảng <2, 3, 8, 6, 1>.
b. Mảng nào với các thành phần của tập hợp {1, 2,. . n} có nhiều phép nghịch đảo nhất? Có bao nhiêu?
c. Nêu mối quan hệ giữa thời gian thực hiện của kỹ thuật sắp xếp chèn và sốlượng phép nghịch đảo trong mảng đầu vào? Xác minh câu trả lời.
d. Cho một thuật toán xác định số lượng phép nghịch đảo trong một phép hoán vị bết kỳ trên n thành phần trong 0(« lg n) thời gian ca xấu nhất. (Mách nước: Sửa đổi phương pháp sắp xếp trộn.)
Có nhiều tài liệu tuyệt vời nói về chủ đề thuật toán nói chung, kể cả các tài liệu của Aho, Hopcroft, và Ưllman [4, 5], Baase [14], Brassard và Bratley [33], Horowitz và Sahni [105], Knuth [121, 122, 123], Manber [142], Mehlhom [144, 145, 146], Purdom và Brown [164], Reingold, Nievergelt, và Deo [167], Sedgewick [175], và Wilf [201]. Bentley [24, 25] và Gonnet [90] có mô tả vài khía cạnh thực tiễn hơn về thiết kế thuật toán.
Vào năm 1968, Knuth xuất bản tập đầu tiên trong ba tập có tiêu đề chung là The Art of Computer Programming[121, 122, 123]. Tập đầu tiên đã đánh dấu sự khởi đầu trong tiến trình nghiên cứu hiện đại các thuật toán máy tính tập trung vào việc phân tích thời gian thực hiện, và .
trọn bộ là tài liệu tham khảo quý giá và hấp dẫn đối với nhiều chủ đề trình bày ở đây. Theo Knuth, từ“algorithm” xuất phát từ tên “al- Khowarizmi,” một nhà toán học Ba-tư vào thế kỷ thứ chín.
Aho, Hopcroft, và Ullman [4] đãủng hộ phương pháp phân tích tiệm cận của các thuật toán như một biện pháp để so sánh khả năng thực hiện tương đối. Họ cũng đã phổ biến cách dùng các quan hệ truy toán để mô tả các thời gian thực hiện của các thuật toán đệ quy.
Knuth [123] cung cấp một cách giải quyết bách khoa của nhiều thuật toán sắp xếp. Phép so sánh các thuật toán sắp xếp của ông ta (trang 421) có gộp các tiến trình phân tích đếm bước chính xác, giống như kiểu mà ta đã thực hiện ở đây đối với phương pháp sắp xếp chèn. Phần mô tả của Knuth về sắp xếp chèn bao hàm vài biến thể của thuật toán. Mà quan trọng nhít là kiểu sắp xếp Shell [Shell’s sort], do D. L. Shell giới thiệu, sử dụng kỹ thuật sắp xếp chèn trên các dãy con định kỳ của đầu vào để tạo ra một thuật toán sắp xếp nhanh hơn.
Các bạn có thể dùng thuật toán để viết code cho landing page nhắm tối ưu hoá trang đích tăng tỷ lệ chuyển đổi
Sắp xếp trộn cũng được Knuth mô tả. Ông cho biết một máy so phiếu đục lỗ cơ học có khả năng trộn hai cỗ bài gồm các lá bài đục lỗ trong một lượt xêp đã được sáng chế vào năm 1938. J. von Neumann, một trong những người tiên phong về khoa học máy tính, dường như đã viết một chương trình cho kỹ thuật sắp xếp trộn trên máy tính EDVAC vào năm 1945.