Khi một thuật toán chứa một lệnh gọi đệ quy lên chính nó, thời gian thực hiện của nó thường được mô tả bởi một phương trình truy toán hoặc phép truy toán, mô tá thời gian thực hiện chung trên một bài toán có kích cỡn theo dạng thời gian thực hiện trên các đầu vào nhỏ hơn. Như vậy, có thể dùng các công cụ toán học để giải quyết phép truy toán và cung cấp các giới hạn về khả năng thực hiện của thuật toán.
Một phép truy toán của thời gian thực hiện trong một thuật toán chia để trị thường dựa trên ba bước kiểu mẫu căn bản. Cũng như trước, giả sửT(n) là thời gian thực hiện trên một bài toán có kích cỡn. Nếu kích cỡ bài toán đủ nhỏ, giả sửn < c với một hằng c nào đó, nghiệm đơn giản sẽ bỏ ra một thời gian bất biến, mà ta viết là 0(1). Giá sử ta chia Jay sắp xcp
aT(rưb) + D(n) = C(n) bằng không nếu n< c,bài toán thành a bài toán con, mỗi bài có Mbkích cỡ so với bài toán ban đầu. Nếu lấy Đ(n) thời gian để chia bài toán thành các bài toán con và C(n) thời gian để tể hợp các nghiệm của các bài toán con thành nghiệm cho bài toán ban đầu, ta sẽ có phép truy toán
Trong Chương 4, ta sẽ xem cách giải quyết các phép truy toán chung theo dạng này.
Phân tích kỹ thuật sắp xếp trộn
Tuy mã giả của MERGE-SORT ỉàm việc đúng đắn khi sô” ỉượng thành phần không đều, song ta có thể đơn giản hóa tiến trình phân tích gốc- phép truy toán nếu như mặc nhận kích cỡ bài toán ban đầu là một lũy thừa của hai. Như vậy, mỗi bước chia cho ra hai dãy con có kích cỡ chính xác là n/2. Trong Chương 4, ta sẽ thấy giả thiết này không ảnh hưởng đến câ”p tăng trưởng của giải pháp đối với phép truy toán.
Dưới đây là cách suy luận để xác lập phép truy toán cho T(n\ là thời gian thực hiện trường hợp xâu nhất của phương pháp sắp xếp trộn trên n con số. Tiến trình sấp xếp trộn trên chỉ một thành phần sẽ bỏ ra một thời gian bất biến. Khi có n>1 thành phần, ta tách nhỏ thời gian thực hiện như sau.
Chia: Bước chia chỉ tính toán điểm giữa của mảng con, bỏ ra một thời gian bâ”t biến. Do đó, D(n) = 0(1).
Trị: Ta giải quyết đệ quy hai bài toán con, mỗi bài có kích cỡn/2, đóng góp 2T(n/2) vào thời gian thực hiện.
Tổ hợp: Ta đã lưu ý thủ tục MERGE trên một mảng con n-thành phần bỏ ra một thời gian 0(n), do đó C(n) = 0(/ĩ).
Khi cộng các hàm D(n) và C{n) của đợt phân tích sắp xếp trộn, ta đang cộng một hàm là 0(n) và một hàm là 0(1). Tổng này là một hàm tuyến tính của ny tức, 0 (nị Việc cộng nó với số hạng 2T{rư2) của bước “trị” [conquer] sẽ cho ra phép truy toán cho thời gian thực hiện trường hợp xâu nhất T(n) của kỹ thuật sắp xếp trộn:
2T(n/2) + 0(rt) nếu n > 1.0(1) nếu n~1,
Trong Chương 4, ta sẽ thấy Tịn) là G(n lg n\ ở đó lg n thay cho log n. Nếu các đầu vào đủ lớn, !*> thuật sắp xếp trộn, với thời gian thực hiện 0(n lg n) của nó, tỏ ra trội vượt so với kỹ thuật sắp xếp chèn, có thời gian thực hiện là G(n2) trong trường hợp xấu nhất.
Bài tập
13-1
Dùng Hình 1.3 làm mẫu, minh họa phép toán sắp xếp trộn trên mảng A = <3, 41, 52, 26, 38, 57, 9, 49>.
13-2
Viết mã giả của MERGE(A, p, q, r).
13-3
Dùng phép quy nạp toán học để nêu rõ nghiệm của phép truy toán
7»=í2 níu“=2:
[ 2T{n/2) + n nếu n > 2*, k > 1.
là r (n) = rtlg/2.
13-4
Sắp xếp chèn có thể được diễn tả dưới dạng một thủ tục đệ quy như sau. Để sắp xếp A[l„n], ta sắp xếp theo đệ quy A[l..fl – 1] rồi chèn A[n\ vào mảng đã sáp xếp A[l.,n – 1 ]. Viết một phép truy toán cho thời gian thực hiện của phiên bản đệ quy này của kỹ thuật sắp xếp chèn.
13-5
Quay lại bài toán tìm kiếm (xem Bài tập 1.1 -3), nhận thấy nếu dãy A được sắp xếp, ta có thể kiểm tra điểm giữa của dãy theo V và loại bỏ phân nửa dãy không cần xét thêm. Tìm nhị phân[binary search] là một thuật toán lặp lại thủ tục này, mỗi lần chia đôi kích cỡ phần còn lại của dãy. Viết mã giả, lặp lại hoặc đệ quy, cho kỹ thuật tìm nhị phân. Chứng tỏ thời gian thực hiện trường hợp xấu nhất của kỹ thuật tìm nhị phân là 0(lg nị
13-6
Nhận thấy vòng lặp while của các dòng 5-7 trong thủ tục INSERTION-SORT ở Đoạn 1.1 sử dụng một đợt tìm kiếm tuyến tính để quét (lùi) qua mảng con sắp xếp A [1 .. j – 1]. Có thể dùng kỹ thuật tìm nhị phân (xem Bài tập 1.3- 5) để cải thiện thời gian thực hiện chung trong trường hợp xấu nhất của kỹ thuật sắp xếp chèn theo 0(n lg n) hay không?
13-7*
Mô tả một thuật toán 0(n Ig n)-thời gian đé, cho một tập hợp sgồm nsô thực và một số thực Xkhác, xác định có tồn tại hay không hai thành phần trong scó tổng chính xác là Jt.
- Tóm tắt
Một thuật toán tốt cũng giống như một con dao sắc—nó thực hiện
chính xác những gì cần làm với một nỗ lực tối thiểu. Dùng thuật toán sai để giải quyết một bài toán cũng giống như đang gắng dùng một tua-vít để cắt một miếng thịt nướng: tuy chung cuộc vẫn có thể có một kết quả tiêu hóa được, song bạn phải tốn nhiều nỗ lực hơn mức cần thiết, mà kết quả không mấy thẩm mỹ.
Các thuật toán được sáng chế để giải quyết cùng một bài toán thường khác biệt đáng kể về hiệu năng. Những khác biệt này có thể có ý nghĩa hơn nhiều so với sự khác biệt giữa một máy tính cá nhân và một siêu máy tính. Ví dụ, hãy để một siêu máy tính chạy phương pháp sắp xếp chèn đấu với một máy tính cá nhân nhỏ chạy phương pháp sắp xếp trộn. Chúng phải sắp xốp một mảng gồm một triệu con sấ Giả sử siêu máy tính thi hành 100 triệu chỉ lệnh ợiỗi giây, trong khi máy tính cá nhân chỉ thi hành một triệu chỉ lệnh mỗi giây. Để phóng đại thêm sự khác biệt này, ta giả sử một lập trình viên lanh lợi nhất thế giới đã mả hóa kỹ thuật sắp xếp chèn bằng ngôn ngữ máy cho siêu máy tính, và mã kết quả đó yêu cầu 2n2 chỉ lệnh siêu máy tính để sắp xếp n con số. Mặt khác, kỹthuật sắp xếp trộn được một lập trình viên trung bình viết mã cho máy tính cá nhân bằng một ngôn ngữ cấp cao với một trình biên dịch không mấy hiệu quả, và mã kết quả sử dụng 50n lg n chỉ lệnh máy tính cá nhân. Để sấp xếp một triệu con số, siêu máy tính bỏ ra
Các bạn có thể ứng dụng thuật toán để viết phần mềm quản lý các dịch vụ.
Ví dụ viết phần mềm quản lý dịch vụ chuyển phát nhanh. Giúp cho Dịch vụ chuyển phát nhanh hỏa tốc trong ngày nhanh chóng và chính xác hơn