Hướng dẫn giải Vận dụng 1 Bài 24. Đánh giá độ phức tạp thời gian thuật toán (trang 111) – SGK Tin học 11 Kết nối tri thức. Tham khảo: Vận dụng kiến thức thực tế của bản thân để trả lời câu hỏi.
Câu hỏi/Đề bài:
Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong bài 21.
Hướng dẫn:
Vận dụng kiến thức thực tế của bản thân để trả lời câu hỏi.
Lời giải:
Số lần so sánh giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần so sánh giữa các phần tử là cố định, không phụ thuộc vào dữ liệu đầu vào. Cụ thể, số lần so sánh trong thuật toán sắp xếp chọn là n(n-1)/2, với n là số tử trong mảng hoặc danh sách.
Số lần hoán đổi giữa các phần tử: Trong thuật toán sắp xếp chọn, số lần hoán đổi giữa các phần tử có thể đạt đến tối đa n-1 lần, với n là số phần tử trong mảng hoặc danh sách.
Vậy độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n^2), hay n(n-1)/2 lần so sánh và tối đa n-1 lần hoán đổi giữa các phần tử.