Mục lục bài họcĐang ở d04-b2
Standard Algorithms, Data Structures and Efficiency
Arrays and collections. An array stores elements of the same type in contiguous memory with a fixed size, and any element can be reached directly from its index in constant time. A collection in the IB sense is accessed sequentially through the operations addItem, getNext, resetNext, hasNext and isEmpty; it can grow, but elements cannot be reached by index. The choice follows from the access pattern: use an array when you need direct access by position or a fixed-size table, and a collection when the number of items is unknown and you only ever process them one after another.
Searching. Linear search examines elements one at a time. It works on unsorted data and on structures that can only be traversed sequentially, needs one comparison in the best case and n in the worst. Binary search repeatedly halves the remaining range, so it needs about log base 2 of n comparisons — around 20 for a million elements — but it requires sorted data and direct access by index. The decision therefore depends on how many searches will be performed: sorting first is only worth it if the cost is spread over many later searches.
Sorting. Bubble sort repeatedly passes through the data swapping adjacent elements that are out of order; it is simple and can stop early on nearly sorted data, but in general it performs on the order of n squared comparisons. Selection sort finds the smallest remaining element on each pass and puts it in place; it always performs the same number of comparisons but far fewer swaps, which matters when moving an element is expensive. Both are quadratic, so both become impractical well before a million elements, which is why real systems use algorithms of order n log n.
Reasoning about efficiency. Count the operations as a function of input size and keep only the dominant term. A single loop over n items is linear; a loop nested inside another is quadratic; halving the problem each step is logarithmic. State which case you are describing, since best, average and worst can differ sharply — bubble sort on already-sorted data with an early-exit check is linear, while its worst case is quadratic. Finally, remember that time is not the only resource: an algorithm can trade memory for speed, and on real hardware an algorithm with worse theoretical complexity can win if it has better locality of reference.
Mảng và tập hợp. Mảng lưu các phần tử cùng kiểu trong vùng nhớ liền kề với kích thước cố định, và truy cập trực tiếp được tới bất kỳ phần tử nào từ chỉ số của nó trong thời gian hằng số. Tập hợp theo nghĩa của chương trình IB được truy cập tuần tự qua các thao tác thêm phần tử, lấy phần tử kế tiếp, đặt lại con trỏ duyệt, kiểm tra còn phần tử hay không và kiểm tra rỗng; nó có thể lớn lên, nhưng không truy cập được theo chỉ số. Lựa chọn được quyết định bởi cách truy cập: dùng mảng khi cần truy cập trực tiếp theo vị trí hoặc cần một bảng kích thước cố định, và dùng tập hợp khi chưa biết số phần tử và chỉ bao giờ cũng xử lý lần lượt từng phần tử.
Tìm kiếm. Tìm kiếm tuần tự kiểm tra từng phần tử một. Nó làm việc được trên dữ liệu chưa sắp xếp và trên các cấu trúc chỉ duyệt được tuần tự, cần một phép so sánh trong trường hợp tốt nhất và n phép trong trường hợp xấu nhất. Tìm kiếm nhị phân liên tục chia đôi khoảng còn lại, nên cần khoảng lôgarit cơ số hai của n phép so sánh — chừng 20 phép với một triệu phần tử — nhưng nó đòi hỏi dữ liệu đã sắp xếp và truy cập trực tiếp theo chỉ số. Vì vậy quyết định phụ thuộc vào số lần tìm kiếm sẽ thực hiện: sắp xếp trước chỉ đáng khi chi phí đó được chia cho nhiều lần tìm về sau.
Sắp xếp. Sắp xếp nổi bọt quét đi quét lại qua dữ liệu và đổi chỗ các cặp kề nhau đang sai thứ tự; nó đơn giản và có thể dừng sớm khi dữ liệu gần như đã sắp, nhưng nói chung cần số phép so sánh ở bậc n bình phương. Sắp xếp chọn tìm phần tử nhỏ nhất còn lại ở mỗi lượt rồi đặt nó vào đúng vị trí; nó luôn thực hiện cùng một số phép so sánh nhưng số lần ĐỔI CHỖ ít hơn hẳn, điều này quan trọng khi việc di chuyển một phần tử là tốn kém. Cả hai đều ở bậc bình phương, nên cả hai đều trở nên bất khả thi từ rất lâu trước mức một triệu phần tử — đó là lý do các hệ thống thật dùng các thuật toán ở bậc n nhân lôgarit của n.
Lập luận về hiệu quả. Hãy đếm số phép toán như một hàm của kích thước đầu vào rồi chỉ giữ lại số hạng trội nhất. Một vòng lặp đi qua n phần tử là bậc tuyến tính; một vòng lặp lồng trong một vòng lặp khác là bậc bình phương; chia đôi bài toán ở mỗi bước là bậc lôgarit. Luôn nói rõ đang mô tả trường hợp nào, vì tốt nhất, trung bình và xấu nhất có thể khác nhau rất xa — sắp xếp nổi bọt có kiểm tra dừng sớm chạy ở bậc tuyến tính trên dữ liệu đã sắp, trong khi trường hợp xấu nhất của nó là bậc bình phương. Cuối cùng, hãy nhớ thời gian không phải tài nguyên duy nhất: một thuật toán có thể đổi bộ nhớ lấy tốc độ, và trên phần cứng thật, một thuật toán có độ phức tạp lý thuyết kém hơn vẫn có thể thắng nếu nó có tính cục bộ truy cập tốt hơn.
Một danh sách 10 000 bản ghi chưa sắp xếp. Phép sắp xếp bằng thuật toán bậc bình phương cần khoảng 50 triệu phép so sánh. Tìm kiếm tuần tự cần trung bình 5 000 phép so sánh mỗi lần; tìm kiếm nhị phân cần khoảng 14 phép. Hãy xác định số lần tìm kiếm mà tại đó việc sắp xếp trước bắt đầu có lợi.
Lập bất phương trình. Gọi Q là số lần tìm kiếm. Phương án không sắp xếp tốn 5 000 nhân Q phép so sánh. Phương án sắp xếp trước tốn 50 000 000 cộng 14 nhân Q. Sắp xếp trước có lợi khi 50 000 000 cộng 14Q nhỏ hơn 5 000Q.
Giải. Chuyển vế: 50 000 000 nhỏ hơn 4 986Q, nên Q lớn hơn 50 000 000 chia 4 986, tức Q lớn hơn khoảng 10 028. Kết luận: chỉ khi thực hiện hơn khoảng mười nghìn lần tìm kiếm thì việc sắp xếp trước mới hoàn vốn.
Đọc kết quả cho đúng, vì đây mới là phần được chấm. Con số này nói rằng với một cơ sở dữ liệu tra cứu liên tục — chẳng hạn danh bạ được tra hàng nghìn lần mỗi ngày — sắp xếp là hiển nhiên đúng và chi phí ban đầu không đáng kể. Nhưng với một tệp nhật ký chỉ được tìm vài lần rồi bỏ đi, sắp xếp là lãng phí thuần tuý. Câu trả lời không phải "nhị phân nhanh hơn" mà là chi phí sắp xếp phải được phân bổ cho số lần tìm kiếm.
Ba yếu tố làm thay đổi ngưỡng này và nên nêu để lấy điểm đánh giá. Thứ nhất, nếu dùng thuật toán sắp xếp bậc n nhân lôgarit của n thay vì bậc bình phương, chi phí sắp xếp giảm từ khoảng 50 triệu xuống còn khoảng 130 nghìn phép so sánh, và ngưỡng hoà vốn tụt xuống chỉ còn khoảng 26 lần tìm kiếm — tức lựa chọn thuật toán sắp xếp làm thay đổi kết luận hoàn toàn. Thứ hai, nếu dữ liệu thay đổi thường xuyên thì phải sắp lại hoặc phải duy trì thứ tự khi chèn, và chi phí đó phải được tính vào. Thứ ba, nếu dữ liệu chỉ duyệt được tuần tự, chẳng hạn một danh sách liên kết, thì tìm kiếm nhị phân không dùng được bất kể dữ liệu đã sắp xếp hay chưa, vì nó cần truy cập trực tiếp theo chỉ số.
Hai tình huống. (a) Sắp xếp một danh sách 2 000 bản ghi mà mỗi bản ghi là một khối dữ liệu lớn, nên mỗi lần đổi chỗ rất tốn kém. (b) Sắp xếp lại một danh sách 2 000 số đã gần như đúng thứ tự, chỉ vài phần tử bị lệch. Chọn thuật toán cho từng trường hợp và giải thích.
Trước hết, tách hai đại lượng mà thí sinh hay gộp làm một. Số phép so sánh và số lần đổi chỗ là hai chi phí khác nhau, và hai thuật toán này khác nhau chính ở đại lượng thứ hai.
Sắp xếp chọn. Mỗi lượt duyệt phần chưa sắp để tìm phần tử nhỏ nhất, rồi đổi nó với phần tử ở đầu phần chưa sắp. Số phép so sánh luôn ở bậc n bình phương bất kể dữ liệu ban đầu ra sao, nhưng số lần đổi chỗ chỉ là n trừ một, tức tuyến tính — mỗi lượt đúng một lần đổi.
Sắp xếp nổi bọt. Quét qua danh sách và đổi chỗ mọi cặp kề nhau sai thứ tự. Số lần đổi chỗ trong trường hợp xấu nhất ở bậc n bình phương, cao hơn hẳn. Bù lại, nếu thêm một cờ đánh dấu "lượt này có đổi chỗ nào không" và dừng khi không còn đổi chỗ, thuật toán chỉ cần một lượt duy nhất trên dữ liệu đã sắp — tức bậc tuyến tính.
(a) Bản ghi lớn, đổi chỗ tốn kém — chọn sắp xếp chọn. Vì chi phí bị chi phối bởi việc di chuyển dữ liệu chứ không phải bởi việc so sánh, đại lượng cần tối thiểu hoá là số lần đổi chỗ. Sắp xếp chọn thực hiện đúng 1 999 lần đổi chỗ, trong khi sắp xếp nổi bọt có thể thực hiện hàng triệu. Ghi chú thực tiễn đáng nêu: một giải pháp tốt hơn nữa là sắp xếp một mảng các tham chiếu tới bản ghi thay vì di chuyển chính bản ghi, khi đó chi phí đổi chỗ trở nên không đáng kể và tiêu chí lựa chọn quay về số phép so sánh.
(b) Dữ liệu gần như đã sắp — chọn sắp xếp nổi bọt có cờ dừng sớm. Đây là trường hợp duy nhất mà sắp xếp nổi bọt thực sự thắng. Với dữ liệu gần đúng thứ tự, chỉ cần một vài lượt là không còn cặp nào sai thứ tự và thuật toán dừng, cho chi phí gần với bậc tuyến tính. Sắp xếp chọn không tận dụng được điều này: nó luôn duyệt hết phần chưa sắp ở mỗi lượt nên vẫn tốn bậc bình phương ngay cả khi dữ liệu đã sắp hoàn hảo.
Nguyên tắc rút ra. Đừng so sánh hai thuật toán bằng một con số duy nhất. Hãy hỏi chi phí nào chi phối trong tình huống này — so sánh hay di chuyển — và dữ liệu đầu vào có tính chất đặc biệt nào không. Hai câu hỏi đó gần như luôn chỉ thẳng tới một lựa chọn.
Bẫy 2 — gộp số phép so sánh với số lần đổi chỗ. Sắp xếp chọn và sắp xếp nổi bọt có cùng bậc về số phép so sánh nhưng khác hẳn về số lần đổi chỗ, và chính điều đó quyết định lựa chọn khi việc di chuyển dữ liệu là tốn kém.
Bẫy 3 — nói về hiệu quả mà không nói đang xét trường hợp nào. Sắp xếp nổi bọt có cờ dừng sớm là bậc tuyến tính ở trường hợp tốt nhất và bậc bình phương ở trường hợp xấu nhất. Không nêu rõ trường hợp thì câu trả lời không được tính là đúng.
Đọc xong rồi — làm thử ngay
Bài tập của chương Computational Thinking, Problem-Solving and Programming gồm 14 câu trắc nghiệm và 5 đề tự luận. Đáp án hiện ngay khi chọn, miễn phí.