Trong kỹ thuật phân tích sắp xếp chèn trên đây, ta đã xem xét cả ca tốt nhất, ỏ đó mảng đầu vào đã được sắp xếp sẩn, lẫn trường hợp xấu nhất, ở đó mảng đầu vào được sắp xếp đảo ngược. Tuy nhiên, với phần còn lại của cuốn sách, ta thường tập trung vào việc chỉ tìm thời gian thực hiện trường hợp xấu nhất; nghĩa là, thời gian thực hiện dài nhất của một đầu vào bất kỳ có kích cỡn. Sở dĩ như vậy là vì ba lý do khả dĩ sau đây.
• Thời gian thực hiện trường hợp xâu nhất của một thuật toán là một cận trên [upper bound] đối với thời gian thực hiện của một đầu vào bất kỳ. Biết rằng nố bảo đảm thuật toán sẽ không bao giờ kéo dài hơn nữa. Ta không cần phải suy đoán này nọ về thời gian thực hiện và hy vọng nó không trở nên tệ hại hơn.
• Với vài thuật toán, trường hợp xấu nhâ’t xảy ra khá thường xuyên. Ví dụ, trong khi tìm kiếm một mẩu thông tin cụ thể trong một cơ sở dữ liệu, trường hợp xâu nhất của thuật toán tìm kiếm thường xảy ra khi thông tin đó không hiện diện trong cơ sở dữ liệu. Trong vài ứng dụng tìm kiếm, ta thường gặp các đợt tìm kiếm thông tin vắng mặt.
Thông thường, “trường hợp trung bình” [average case] cũng tệ hại tương tự như trường hợp xấu nhất. Giả sử, ta ngẫu nhiên chọn ncon số và áp dụng kỹ thuật sắp xếp chèn. Phải mít bao lâu để xác định vị trí chèn thành phần A [ị] trong mảng con A[l..ỳ – 1]? Tính trung bình, phân nửa các thành phần trong A[l.j – 1] là nhỏ hơn A[/], và phân nửa các thành phần là lớn hơn. Như vậy, tính trung bình, ta kiểm tra phân nửa mảng con A[\.J – I], do đó ỉ. – j/2. Nếu tính ra thời gian thực hiện của trường hợp trung bình kết quả, thì hóa ra đó là một hàm bậc hai của kích cỡ đầu vào, hệt như thời gian thực hiện trường hợp xấu nhất.
Trong vài trường hợp cụ thể, ta sẽ quan tâm đến thời gian thực hiện dự trù[expected] hoặc trường hợp trung bình[average case] của một thuật toán. Tuy nhiên, một bài toán có tiến hành phân tích trường hợp trung bình đó là: khi không nắm rõ nội dung tạo thành một đầu vào “trung bình” cho một bài toán cụ thể. Thông thường, ta sẽ mặc nhận rằng tất cả đầu vào có một kích cỡ nhất định có thể xáy ra như nhau. Trong thực tế, giả thiết này có thểbị vi phạm, song đôi lúc một thuật toán ngẫu nhiên hóa có thể buộc phải áp dụng nó.
Câp tăng trưởng
Ta đã dùng vài kiểu trừu tượng giản lược để tạo thuận lợi cho tiến trình phân tích thủ tục INSERTION-SORT. Trước tiên, ta đã bỏ qua mức hao phí [cost] thực tế của từng câu lệnh* dùng các hằng c để biểu thị các hao phí này. Sau đó, ta nhận thấy thậm chí các hằng này còn cho ta nhiều chi tiết hơn mức cần thiết thực tế: thời gian thực hiện ca xíu nhất là an2 + bn+ c với một sô” hằng a, b, và c tùy thuộc vào các hao phí câu lệnh cr Như vậy, ta đã bỏ qua không những các hao phí câu lệnh thực tê, mà cả các hao phí trừu trượng [abstract costs] c..
Giờ đây, ta sẽ xem xét một kiểu trừu tượng giản lược khác. Đó là tốc độ tăng trưởng[rate of growth], hoặc cấp tăng trưởng, của thời gian thực hiện mà ta thực sự quan tâm. Vì vậy, ta chỉ xem xét sô” hạng đầu của một công thức (ví dụ, an2), bởi các số hạng câ”p thâ”p tương đô”i không quan trọng với n lớn. Ta cũng bỏ qua hệ sốbâ”t biến của sô” hạng đầu, bởi các thừa sô” bâ”t biến ít quan trọng hơn tô”c độ tăng trưởng trong khi xác định hiệu năng tính toán của các đầu vào lổn. Do đó, ta viết, chẳng hạn, kỹ thuật sắp xếp chèn có một thời gian thực hiện trường hợp xấu nhát là 0(«2) (đọc là “theta của rt-bình phương”).
Trong chương này, ta đơn giản dùng ký hiệu 0; nó sẽ được định nghĩa một cách chính
Một thuật toán thường được xem là hiệu quả hơn so với một thuật toán khác khi thời gian thực hiện trường hợp xấu nhất của nó có một câp tăng trưởng thấp hơn. Kiểu đánh giá này có thểgặp lỗi đối với các đầu vào nhỏ, song với các đầu vào đủ lớn, thì trong trường hợp xấu nhất một thuật toán như 0(«2) chẳng hạn sẽ chạy nhanh hơn so với một thuật toán 0(rt3).
Bài tập
1.1- 1
Xem xét tiến trình sắp xếp n con sô” lưu trữ trong máng A bằng cách trước tiên tìm thành phần nhỏ nhất của A và đặt nó trong mục đầu tiên của một mảng B khác. Sau đó tìm thành phần nhỏnhâ’t thứ hai của A và đặt nó trong mục thứ hai của B. Tiếp tục như vậy với n thành phần của A. Viết mã giả của thuật toán này, có tên là sắp xếp chọn lọc. Nêu các thời gian thực hiện trường hợp tốt nhất và xâu nhâ’t của kỷ thuật sắp xếp chọn lọc theo hệ ký hiệu .
1.2- 2
Xem xét lại kiểu tìm kiếm tuyến tính (xem Bài tập 1.1-3). Giả định thành phần đang tìm kiếm có khả năng như nhau là một thành phần bất kỳ trong mảng, ta cần kiểm tra trung bình bao nhiêu thành phần của dãy đầu vào? Trong trường hợp xấu nhâ’t thì sao? Nêu các thời gian thực hiện trường hợp xâu nhất và trung bình của kỹ thuật tìm kiếm tuyến tính theo hệ ký hiệu 0 Chứng minh các nghiệm.
1.2- 3
Xem xét bài toán xác định xem một dãy tùy ýn con sô'<xr xv …, x>có chứa các lần xuâ’t hiện lặp lại của một con số nào đó hay không. Dẩn chứng điều này có thể thực hiện theo thời gian 0(n lg rt), ở đó ĩg n là log2n.