btvn.vn
Tìm kiếm Đăng nhập

Đo thời gian sắp xếp trộn và chèn

Lưu trên thiết bị này
Chuyên đề lựa chọn CS: Chia để trị · Chọn bài khác

Hai bản sao của cùng dãy chưa sắp xếp

Đọc dãy A từ tệp trước khi đo. Với mỗi lượt, tạo B=A.copy() và C=A.copy() trước đoạn tính thời gian; không dùng kết quả đã sắp xếp của thuật toán đầu làm đầu vào thuật toán sau. Dùng perf_counter lấy thời điểm trước và sau từng thuật toán. Bản trộn trả dãy nên cần giữ kết quả; bản chèn sửa C nên kiểm C sau khi gọi. Cả hai kết quả cần khớp dãy sắp xếp đúng, đồng thời giữ đủ phần tử. Trong tệp thực hành, benchmark thực hiện các bước ấy và trả thời gian trung bình ms/lần. Tạo bản sao, đọc tệp và kiểm kết quả đều ở ngoài hai đoạn đo.

Thực hiện và đọc bảng số đo

Chạy với tệp mẫu: ```text python3 g11-cs-sap-xep-tron.py do g11-cs-day-can-sap-xep.inp --repeat 100 ``` Bảng có số phần tử n, số lần đo, thời gian trộn và chèn tính bằng ms/lần. Cột nào nhỏ hơn thì thuật toán đó nhanh hơn trong lượt đo này. Có thể đổi dữ liệu thành dãy tăng, giảm hoặc có giá trị trùng và đo lại với cả hai bản trên cùng dữ liệu mới. Tệp mẫu chỉ có 6 phần tử nên chưa đủ đại diện cho dãy lớn. Số đo phụ thuộc dữ liệu, máy, phiên bản Python và nhiễu thời gian; không dùng một lượt nhỏ để kết luận thuật toán luôn nhanh hơn. Trong trường hợp xấu nhất, chèn có O(n²), trộn có O(n log n); chèn có thể chạy tốt khi dãy đã gần hoặc đúng thứ tự.

Bài luyện

Cách chuẩn bị nào giúp so sánh hai thuật toán trên cùng dữ liệu?
Chọn một đáp án

Bài luyện

Một lượt đo 6 phần tử cho chèn nhanh hơn trộn. Kết luận nào phù hợp?
Chọn một đáp án

Bài luyện

Vì sao cần giữ result=mergeSort(B) trong phép đo?
Chọn một đáp án

Đang học