Giáo trình thuật toán lý thuyết và bài tập sơ cấp đến cao cấp - Nhà xuất bản Thống kê

Tài liệu giáo trình thuật toán cung cấp kiến thức toàn diện từ sơ cấp đến cao cấp, kết hợp hệ thống bài tập thực hành dành cho sinh viên công nghệ thông tin.

• Tác giả: Ngọc Anh Thư
• Trường học: Nhà Xuất Bản Thống Kê
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giáo trình thuật toán lý thuyết và bài tập sơ cấp - trung cấp - cao cấp
• Loại tài liệu: Giáo trình
• Năm xuất bản: 2002

Tóm tắt

I. Tổng quan về giáo trình thuật toán lý thuyết và bài tập

Giáo trình thuật toán lý thuyết và bài tập do Nhà xuất bản Thống kê ấn hành là một công trình dịch thuật đồ sộ. Cuốn sách phục vụ nhu cầu đào tạo công nghệ thông tin tại Việt Nam. Nội dung sách được xây dựng từ nền tảng kinh điển quốc tế. Tác phẩm kết hợp hài hòa giữa lý thuyết hình thức và bài toán thực tế. Toàn bộ tài liệu chia thành nhiều cấp độ học trình. Cấu trúc bài giảng đi từ sơ cấp, trung cấp đến cao cấp. Mỗi chương sách hoạt động như một đơn vị học phần độc lập. Cách thiết kế này tạo điều kiện thuận lợi cho việc tổ chức chương trình giảng dạy. Các khái niệm toán học phức tạp được giải thích rõ ràng và mạch lạc. Bên cạnh đó, cuốn sách tích hợp kho tài nguyên bài tập phong phú. Hơn chín trăm bài tập tự luyện và hơn một trăm hai mươi bài toán điển cứu được chọn lọc kỹ lưỡng. Hệ thống này giúp củng cố kiến thức logic chặt chẽ. Giáo trình đóng vai trò như một cuốn cẩm nang kỹ thuật thiết yếu cho mọi kỹ sư phần mềm.

1.1. Xuất bản và đội ngũ dịch thuật Nhà xuất bản Thống kê

Cuốn sách được chủ biên bởi chuyên gia Ngọc Anh Thư cùng nhóm biên dịch giàu kinh nghiệm. Đội ngũ gồm các học giả Nguyễn Tiến, Nguyễn Văn Hoài, Nguyễn Hữu Bình, Đặng Xuân Hường, Ngô Quốc Việt và Trương Ngọc Vân. Bản dịch tiếng Việt được xuất bản bởi Nhà xuất bản Thống kê. Công trình này chuyển ngữ công phu từ giáo trình thuật toán chuẩn quốc tế. Nhóm dịch chú trọng tính chính xác của thuật ngữ chuyên ngành công nghệ thông tin. Các thuật ngữ toán học và khoa học máy tính được đối chiếu cẩn trọng. Văn phong tiếng Việt bảo đảm sự trang trọng và chuẩn xác. Đây là tài liệu quý giá xuất hiện trong giai đoạn giáo trình thuật toán trong nước còn khan hiếm.

1.2. Phân tầng kiến thức từ sơ cấp đến cao cấp

Giáo trình phân chia nội dung theo lộ trình sư phạm rất khoa học. Khối kiến thức khởi đầu bằng các khái niệm cơ bản về cấu trúc dữ liệu. Độc giả tiếp cận với kỹ thuật tìm kiếm tuyến tính và sắp xếp chèn. Sau đó, giáo trình nâng dần độ khó lên mức trung cấp và cao cấp. Các chủ đề nâng cao bao gồm phân tích khấu trừ và thuật toán song song. Cấu trúc mô-đun hóa cho phép từng chương vận hành độc lập. Giảng viên có thể linh hoạt chọn chương giảng dạy phù hợp theo từng học kỳ. Sinh viên cũng dễ dàng tra cứu kiến thức chuyên sâu theo nhu cầu nghiên cứu học thuật cá nhân.

II. Phân tích giáo trình thuật toán lý thuyết và bài tập chi tiết

Việc tiếp cận lý thuyết giải thuật luôn là trở ngại lớn đối với sinh viên ngành khoa học máy tính. Nhiều tài liệu thuật toán trên thị trường thường gặp phải một trong hai khiếm khuyết lớn. Một số cuốn sách quá thiên về chứng minh toán học trừu tượng. Lối viết này khiến người học khó hình dung cách lập trình thực tế. Ngược lại, một số tài liệu chỉ chú trọng kỹ năng viết mã đơn thuần. Phương pháp đó bỏ qua việc đánh giá độ phức tạp thuật toán và hiệu năng dài hạn. Giáo trình này giải quyết triệt để sự mất cân đối trên. Tác phẩm phân tích chi tiết bản chất của từng thuật toán. Cuốn sách không dừng lại ở mô tả trực giác. Các tác giả đi sâu vào chứng minh tính đúng đắn và giới hạn tiệm cận. Hiện tượng tăng trưởng của hàm số được khảo sát nghiêm ngặt qua các trường hợp tốt nhất, trung bình và xấu nhất. Hơn nữa, người học thường gặp lúng túng khi đánh giá tính khả thi của giải thuật trên dữ liệu lớn. Giáo trình chỉ rõ những ngộ nhận phổ biến trong việc sử dụng ký hiệu tiệm cận. Cuốn sách tạo ra một khung nhận thức vững chắc giúp loại bỏ những nhận định thiếu căn cứ học thuật.

2.1. Rào cản toán học trong phân tích độ phức tạp thời gian

Phân tích tiệm cận đòi hỏi nền tảng giải tích và đại số vững chắc. Đa số sinh viên cảm thấy quá tải trước các định lý toán học phức tạp. Việc xác định hàm bao trên và bao dưới thường gây nhầm lẫn nghiêm trọng. Điển hình là sự nhập nhằng giữa ký hiệu Big-O và ký hiệu Theta chuẩn. Sinh viên thường đưa ra những phát biểu vô nghĩa về cận thời gian thực thi. Giáo trình tháo gỡ khó khăn này bằng cách đưa ra định nghĩa toán học rõ ràng. Từng hằng số và ngưỡng giá trị đều có lý giải chi tiết. Nhờ vậy, người học hiểu rõ bản chất của sự tăng trưởng hàm số.

2.2. Sự mất cân bằng giữa lý thuyết và triển khai mã lệnh

Nhiều lập trình viên có thể viết mã nhanh nhưng thiếu tư duy tối ưu hóa giải thuật. Mã nguồn vận hành tốt trên tập dữ liệu thử nghiệm nhỏ. Tuy nhiên, hệ thống sụp đổ khi lượng dữ liệu bùng nổ trong thực tế. Sự thiếu hụt kỹ năng phân tích trường hợp xấu nhất gây ra hậu quả nghiêm trọng. Nhiều phần mềm tiêu tốn tài nguyên bộ nhớ quá mức cho phép. Nhiều dự án thất bại vì chọn sai cấu trúc dữ liệu nền tảng. Giáo trình đặt trọng tâm vào việc đánh giá đánh đổi giữa thời gian và không gian lưu trữ. Đây là vấn đề cốt lõi mà mọi kỹ sư cần nắm vững trước khi phát triển sản phẩm.

III. Phương pháp từ giáo trình thuật toán lý thuyết và bài tập

Giáo trình cung cấp một phương pháp luận sư phạm chặt chẽ và nhất quán. Tác phẩm sử dụng ngôn ngữ mã giả chuẩn hóa làm phương tiện truyền đạt chính. Mã giả loại bỏ sự ràng buộc vào cú pháp cụ thể của từng ngôn ngữ lập trình. Lập trình viên C, Pascal hay Java đều có thể tiếp thu thuật toán một cách trực quan. Phương pháp này nhấn mạnh logic cốt lõi thay vì các chi tiết kỹ thuật phần cứng rườm rà. Bên cạnh mã giả, cuốn sách định hình tư duy giải quyết vấn đề qua các bước mẫu mực. Mỗi thuật toán đều khởi đầu với bài toán phát biểu tường minh. Tác giả trình bày ý tưởng trực giác kèm hình minh họa trực quan. Tiếp theo là các bước triển khai chi tiết qua mã giả có chú giải rõ ràng. Sau cùng là phần chứng minh toán học và phân tích thời gian chạy chi tiết. Đặc biệt, kỹ thuật thiết kế thuật toán được tổng hợp thành những mô hình kinh điển. Phương pháp gia số trong sắp xếp chèn là một ví dụ điển hình. Quy tắc Horner trong việc tính giá trị đa thức giúp tiết kiệm số phép nhân tối đa. Nhờ phương pháp này, người học hình thành bản năng tư duy giải thuật có hệ thống.

3.1. Chuẩn hóa mã giả và phân tích tiệm cận khoa học

Việc sử dụng mã giả đem lại tính phổ quát cao trong đào tạo học thuật. Cú pháp mã giả trong sách rất gọn gàng và dễ hiểu. Người đọc nắm bắt nhanh cấu trúc điều khiển và khối lệnh. Cùng với mã giả, sách thiết lập hệ thống ký hiệu tiệm cận chuẩn xác. Các ký hiệu Theta, Big-O và Omega được định nghĩa rõ theo chuẩn toán học. Từng tính chất đơn điệu, hàm sàn và hàm trần đều được làm sáng tỏ. Cách tiếp cận này giúp sinh viên xây dựng thói quen tư duy hình thức nghiêm cẩn. Từ đó, việc xác định độ phức tạp tính toán trở nên chuẩn xác hơn.

3.2. Rèn luyện tư duy qua kho bài tập và bài toán điển cứu

Kho tài nguyên chín trăm bài tập tạo nên sức mạnh đặc biệt của giáo trình. Các bài tập được phân loại từ mức trắc nghiệm căn bản đến chứng minh chuyên sâu. Độc giả được thử thách với các kỹ thuật sắp xếp chọn lọc và tìm kiếm tuyến tính. Ngoài ra, hơn một trăm hai mươi bài toán điển cứu cung cấp các tình huống ứng dụng đa chiều. Người học phải tự chứng minh thời gian thực thi trong trường hợp xấu nhất. Quá trình giải bài tập kích thích khả năng tư duy phản biện độc lập. Người học không chỉ ghi nhớ giải thuật mà còn hiểu sâu sắc nguyên lý hoạt động nội tại.

IV. Ứng dụng của giáo trình thuật toán lý thuyết và bài tập

Giáo trình thuật toán lý thuyết và bài tập giữ giá trị sử dụng lâu dài trong giảng dạy và thực tiễn kỹ thuật. Tác phẩm không đơn thuần là một cuốn sách giáo khoa đại học. Cuốn sách là tài liệu gối đầu giường của các chuyên gia phát triển phần mềm. Nền tảng tư duy trong sách trang bị năng lực giải quyết các bài toán kỹ thuật phức tạp trong thế giới thực. Trong môi trường học thuật, cuốn sách là khung chuẩn cho các môn học cấu trúc dữ liệu và giải thuật. Giảng viên có thể khai thác từng đơn vị học trình độc lập để biên soạn bài giảng. Sinh viên sử dụng tài liệu để chuẩn bị cho các kỳ thi lập trình quốc tế. Lượng bài tập dồi dào cung cấp nguồn đề thi và đề tài nghiên cứu lý tưởng. Đối với ngành công nghiệp phần mềm, các nguyên lý trong giáo trình định hình tư duy tối ưu hóa mã nguồn. Kỹ sư có thể lựa chọn thuật toán phù hợp cho các hệ thống chịu tải cao. Việc nắm vững phân tích khấu trừ và thuật toán phân tán giúp xây dựng những kiến trúc dữ liệu bền vững. Giáo trình này là chiếc cầu nối hoàn hảo giữa lý thuyết hàn lâm và kỹ nghệ thực hành.

4.1. Tài liệu nền tảng cho giảng dạy và thi đấu lập trình

Tại các trường đại học, giáo trình hỗ trợ thiết kế các học phần giải thuật từ năm hai đến sau đại học. Sinh viên được rèn luyện kỹ năng phân tích thuật toán một cách bài bản. Hệ thống bài tập là nguồn tư liệu chuẩn mực cho các kỳ thi học sinh giỏi và Olympic tin học sinh viên. Các bài toán sắp xếp, đồ thị và quy hoạch động rèn luyện tư duy phản xạ logic. Nhiều câu lạc bộ thuật toán xem cuốn sách như kim chỉ nam cho lộ trình ôn luyện. Tài liệu giúp người học tự tin vượt qua các vòng phỏng vấn kỹ thuật khắt khe tại các tập đoàn công nghệ lớn.

4.2. Cẩm nang thiết kế kỹ thuật cho chuyên gia phần mềm

Trong môi trường sản xuất phần mềm, hiệu năng hệ thống quyết định trực tiếp tới chi phí vận hành. Kỹ sư giàu kinh nghiệm thường tra cứu giáo trình để tối ưu các thành phần cốt lõi. Sách cung cấp các phương án thay thế thực tiễn cho nhiều bài toán kinh điển. Việc hiểu rõ độ phức tạp giúp đội ngũ phát triển tránh được những sai lầm thiết kế tốn kém. Cuốn sách không chỉ hướng dẫn viết mã chạy được mà hướng tới việc xây dựng phần mềm tối ưu và mở rộng linh hoạt. Đây thực sự là cẩm nang kỹ thuật hữu ích luôn có mặt trên bàn làm việc của mỗi chuyên gia.

Trích đoạn nội dung tài liệu

Chương 1 Giới thiệu công nghệ thực thi, kể cả mô hình cho các tài nguyên của công nghệ đó và các chi phí của chúng. Đa phần tập sách này mặc nhận sử dụng mô hình điện toán RAM (random-access machine = máy truy cập ngẫu nhiên), một bộ xử lý chung, làm công nghệ thực thi và ngầm hiểu rằng các thuật toán sẽ được thực thi đưới dạng các chương trình máy tính. Trong mô hình RAM, các chỉ lệnh được thi hành lần lượt, mà không có các phép toán đồng thời. Tuy nhiên, trong các chương sau, ta sẽ có dịp nghiên cứu các mô hình của các máy tính song song và phần cứng số hóa.

Quá trình phân tích luôn là một thách thức, thậm chí với một thuật toán đơn giản. Các công cụ toán học cần thiết có thể gồm cả toán học tổ hợp trừu tượng, lý thuyết xác suất căn bản, kỹ năng về đại số, và khả năng định danh các số hạng quan trọng nhất trong một công thức. Do cách ứng xử của một thuật toán có thể khác nhau đối với từng đầu vào khả dĩ, nên ta cần có một biện pháp để tóm lược cách ứng xử thành các công thức đơn giản và dễ hiểu. Cho dù thông thường chỉ lựa mô hình một máy để phân tích một thuật toán nào đó, song ta vẫn phải đối mặt với nhiều chọn lựa khi quyết định cách diễn tả tiến trình phân tích.

Một mục tiêu tức thời đó là tìm một biện pháp diễn tả đơn giản để viết và điều tác [manipulate], nêu các đặc tính quan trọng của các yêu cầu tài nguyê n của một thuật toán, và hủy bỏ các chỉ tiết dài dòng. Phân tích kỹ thuật sắp xếp chèn Thời gian kéo dài của thủ tục INSERTION-SORT thường tùy thuộc vào đầu vào: tiến trình sắp xếp một ngàn con số sẽ lâu hơn tiến trình sắp xếp ba con số. Vả lại, INSERTION-SORT có thể sử dụng các thời lượng khác nhau để sắp xếp hai dãy đâu vào có kích cỡ giống nhau, tùy thuộc vào mức độ sắp xếp sắn của chúng. Nói chung, thời gian thực hiện của một thuật toán thường tăng theo kích cỡ đầu vào, do đó theo truyền thống, ta thường mô tả thời gian thực hiện của một chương trình như một hàm kích cỡ đầu vào của chương trình đó.

Để thực hiện, ta cần định nghĩa các thuật ngữ “thời gian thực hiện” [running time] và “kích cỡ đầu vào” [size of input] cẩn thận hơn. Ý niệm thích hợp nhất của kích cỡ đầu vào thườ ng tùy thuộc vào bài toán đang nghiên cứu. Với nhiều bài toán, như sắp xếp hoặc tính toán các phép biến đổi Fourier, số đo tự nhiên nhất đó là số lượng các mục : _ 12 Phân tích Các Thuật toán 25 trong đầu vào—ví dụ, kích cỡ mắng n để sắp xếp. Với nhiều bài toán khác, như nhân hai số nguyên, số đo tốt nhất của kích cỡ đầu vào lại là tổng số bit cần thiết để biểu thị đầu vào theo hệ ký hiệu nhị phân bình thường.

Đôi lúc, việc mô tả kích cỡ đầu vào bằng hai con số thay vì một lại tổ ra thích hợp hơn. Ví dụ, nếu đầu vào cho một thuật toán là một đồ thị, kích cỡ đầu vào có thể được mô tả bởi các số đỉnh [vertices} và các cạnh trong đồ thị. Ta sẽ nêu rõ kiểu đo kích cỡ đầu vào sẽ được dùng với từng bài toán mà ta nghiên cứu. Thời gian thực hiện [running time] của một thuật toán trên một đầu vào cụ thể chính là số lượng phép toán nguyên tố [primitive operations] hoặc “các bước” [steps] được thi hành.

Sẽ tiện dụng hơn nếu ta định nghĩa khái niệm “bước” để nó càng độc lập máy càng tốt. Trước mắt, hãy chấp nhận quan điểm sau. Cần có một thời lượng bất biến để thi hành từng dòng mã giả của chúng ta. Dòng này có thể mất một thời lượng khác với dòng kia, song ta mặc nhận rằng từng đợt thi hành dòng thứ ¿ sẽ mất một thời gian c„ ở đó c, là một hằng.

Quan điểm này phù hợp với mô hình RAM, và nó cũng phản ánh cách thực thi mã giả trên hầu hết các máy tính hiện nay?. Trong đoạn mô tả dưới đây, cách diễn tả của chúng ta về thời gian thực hiện của INSERTION-SORT sẽ tiến hóa từ một công thức hỗn độn sử dụng tất cả mọi hao phí câu lệnh c, thành một hệ ký hiệu đơn giản hơn nhiều, dễ dàng điều tác và súc tích hơn. Hệ ký hiệu đơn giản này cũng sẽ giúp ta dễ dàng xác định xem thuật toán này có hiệu quả hơn thuật toán kia hay không. Để bắt đầu, ta trình bày thủ tục INSERTION-SORT bằng các mức “hao phí” thời gian của từng câu lệnh và số lần thi hành từng câu lệnh.,n, ở đó n = length{A], ta giả sử ¡,là số lần thi hành đợt trắc nghiệm vòng lặp while trong dòng 5 theo giá trịjđó.

Ta mặc nhận rằng các chú giải không phải là các câu lệnh thi hành, và do đó không mất thời gian. 3 Ở đây có vài điểm tỉnh tế. Các bước tính toán mà ta đặc tả bằng tiếng Anh thường là các biến thể của một thủ tục yêu cầu không chỉ một thời lượng bất biến. Ví dụ, ở phân sau trong cuốn sách này, ta có thể nói “sort the points by x-coordinate” Ísắp xếp các điểm theo tọa độ x], mà như sẽ thấy, sẽ vận dụng nhiễu hơn một thời lượng bất biến.

Ngoài ra cũng lưu ý, một câu lệnh gọi một chương trình con sẽ mất một thời lượng bất biến. tuy rằng raêt khi được triệu gọi, chương trình con có thể mất nhiều thời gian hơn. Nghĩa là, ta tách riêng tiến trình gọi chương trình con—chuyền các tham số cho nó, vân vân—với tiến trình #f hành: chương trình con đđ. - : 26 Chương 1 Giới thiệu INSERTION-SORT(4) CoSfS times Ifor j — 2 to length [A] C, " p) do key — A[ ] GỒ n=Í 3 > chèn Al7 ] vào chuỗi có sắp xếp P sequence A[I.:0~)) 8 A[i+ l] — key C n_—Ì Thời gian thực hiện của thuật toán là tổng các thời gian thực hiện của từng câu lệnh được thi hành; một câu lệnh trải qua các bước c, để thi hành và được thi hành ø lần sẽ đóng góp cw vào tổng thời gian thực hiện.

Để tính 7(n), thời gian thực hiện của INSERTION-SORT, ta tổng cộng các tích của các cột cosís và £mes, thành Tín) = cạn + c(n~— 1)+€j(n -1)+ c, Du Ẳ DI + c; 3(;1)+ c¿ (n-1) Thậm chí với các đầu vào có một kích cỡ nhất định, thời gian thực hiện của một thuật toán có thể tùy thuộc vào việc cho đầu vào nào có kích cỡ đó. Ví dụ, trong INSERTION-SORT, trường hợp tốt nhất xảy ra khi mảng đã được sắp xếp sẵn., n, ta thấy rằng A[z] < key trong dòng 5 khi ¿ có giá trị ban đầu là j - 1. n, và thời gian thực hiện trong trường hợp tốt nhất là: Tím) = cạn + cj(n - |) + c(n - ]) + cn - L) + cán — 1) =((,+c,+,+é, + c)n- (03‹€®c.*# dc: Thời gian thực hiện này có thể được diễn tả là: an + b với các hằng a và b, tùy thuộc vào hao phí câu lệnh c; do đó nó là một hàn tuyến tính của n. Nếu mảng được sắp xếp theo thứ tự đảo ngược—nghĩa là, theo thứ tự giảm—trường hợp xấu nhất sẽ xẩy ra.

Ta phải so sánh mỗi thành phần A[7] với mỗi thành phần trong nguyên cả mảng con đã sắp xếp A[I./ — 1], và như vậy f, = 7 vớij= 2, 3,. Lưu ý rằng '3 á sệ : 2 -_ Đặc tính này không nhất thiết áp dụng cho một tài nguyên như bộ nhớ. Một câu lệnh tham chiếu mm từ [words] của bộ nhớ và được thi hành n lần không nhất thiết tiêu thụ tổng cộng mm từ của bộ nhớ.9 Phân tích Các Thuật toán n. n(n +Ì xJ= tai j=2 2 và Šu~n= 2E-D trường -_ (Chương 3 sẽ đề cập lại các phép tổng này), ta thấy rằng trong là hợp xấu nhất, thời gian thực hiện của INSERTION-SORT Tín) = cịn+ c(n-1) + cÁn-L) + €¿ (rứeĐ : ) nứ, Đ)+e, (9 tớ Sa bón )*cu(n-]) ưng: = CC: = (§: S+ C S)n tỆtecte+tft# €Ì $ Si+ 9t+c}n -(C; + c¿ + Cy + Œ) diễn tả là Thời gian thực hiện trường hợp xấu nhất này có thể được lần nữa tùy thuộc vào hao an? + bn + c với các hằng a, b, Và c, mà một của n.

phí câu lệnh c„; do đó nó là một hàm bậc hai thời gian thực Thông thường, như trong trường hợp sắp xếp chèn, vào đã cho, mặc dù hiện của một thuật toán được cố định theo một đầu “ngẫu nhiên hóa” [ran- trong các chương sau, ta sẽ gặp các thuật toán thậm chí với cả domized] đáng quan tâm có cách ứng xử có thể thay đổi đầu vào cố định. g bình Phân tích trường hợp xấu nhất và trường hợp trun đã xem xét cả ca Trong kỹ thuật phân tích sắp xếp chèn trên đây, ta lẫn trường hợp xấu tốt nhất, ở đó mảng đầu vào đã được sắp xếp sẵn, Tuy nhiên, với phần nhất, ở đó mảng đầu vào được sắp xếp đảo ngược. chỉ tìm thời gian thực còn lại của cuốn sách, ta thường tập trung vào việc thực hiện dài nhất của một hiện trường hợp xấu nhất; nghĩa là, thời gian ba lý do khả dĩ sau đây. đầu vào bất kỳ có kích cỡ n.

Sở dĩ như vậy là vì thuật toán là một e Thời gian thực hiện trường hợp xấu nhất của một của một đầu vào bất cận trên [upper bound] đối với thời gian thực hiện bao giờ kéo đài hơn nữa. Biết rằng nó bảo đảm thuật toán sẽ không gian thực hiện và hy vọng Ta không cần phải suy đoán này nọ về thời nó không trở nên tệ hại hơn. ra khá thường xuyên. © Với vài thuật toán, trường hợp xấu nhất xảy thể trong một cơ sở dữ Ví dụ, trong khi tìm kiếm một mẩu thông tin cụ kiếm thường xảy ra khi liệu, trường hợp xấu nhất của thuật toán tìm 28 Chương 1 Giới thiệu 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 w con 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[I.,/ - 1]? Tính trung bình, phân nửa các thành phần trong A[I./ - !] là nhỏ hơn A [7], 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[I.