Độ phức tạp thuật toán – O(log n), O(n), O(n log n), O(n²) và cuộc đua sắp xếp

Bài đánh giá thuật toán trong chủ đề Giải quyết vấn đề với sự trợ giúp của máy tính, Tin học 10, đề cập số phép toán theo kích thước dữ liệu, kí hiệu O lớn và so sánh sắp xếp nổi bọt với sắp xếp nhanh. Đồ thị vẽ số bước của log₂n, n, n·log₂n và n² theo n (4 đến 100), kèm số phép so sánh đo thực tế của hai thuật toán sắp xếp. Học sinh kéo con trỏ để đọc giá trị, chọn nhóm đường cần xem và bật trục lôgarit khi các đường chênh nhau quá xa. Bấm Chạy đua, hai thuật toán sắp xếp cùng một dãy với cùng tốc độ bước: sắp xếp nhanh về đích trước, và khoảng cách tăng rõ khi n lớn. Với n nhỏ, chênh lệch không đáng kể, nên độ phức tạp chủ yếu có ý nghĩa khi dữ liệu lớn. Câu hỏi gợi ý: – Khi n tăng gấp đôi, n² tăng bao nhiêu lần? – Vì sao log₂n tăng rất chậm? – Với n = 10, có đáng thay nổi bọt bằng sắp xếp nhanh không?