Với Vận dụng 1 trang 114 giải SGK Tin học 11 Kết nối tri thức chi tiết trong Bài 24: Đánh giá độ phức tạp thời gian thuật toán giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:
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
Vận dụng 1 trang 114 Tin học 11: 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.
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ử.
Xem thêm các bài giải SGK Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Câu hỏi trang 114 Tin học 11: Tính độ phức tạp của các hàm thời gian sau:
Luyện tập 1 trang 114 Tin học 11: Xác định độ phức tạp thời gian cho chương trình sau:
Luyện tập 2 trang 114 Tin học 11: Xác định độ phức tạp thời gian tính toán cho chương trình sau:
Xem thêm các bài giải SGK Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 22: Thực hành bài toán sắp xếp
Bài 23: Kiểm thử và đánh giá chương trình
Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán
Bài 26: Phương pháp làm mịn dần trong thiết kế chương trình
Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
2021 © All Rights Reserved.
