Với giải Hoạt động 3 trang 43 Chuyên đề Tin học 11 Kết nối tri thức chi tiết trong Bài 9: Sắp xếp trộ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 Chuyên đề Tin học 11. Mời các bạn đón xem:
Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn
Hoạt động 3 trang 43 Chuyên đề Tin học 11: Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn
Lời giải:
Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.
Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.
Trường hợp tổng quát
- Tại bước chia (dòng 5), cần O(1) thời gian để thực hiện.
- Các dòng 6, 7 sẽ mất 2T(n/2) thời gian.
- Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).
Tổng kết lại chúng ta các công thức sau tính thời gian T(n).
T(1)=1
T(n) = 2T(n/2) + O(n), n > 1 (1)
Không mất tổng quát, giả sử tồn tại hằng số C > 0 sao cho:
T(n) = 2T (n/2)+ Cn, n > 1 (2)
Các công thức (1), (2) được gọi là công thức truy hồi để tính độ phức tạp thời gian T(n)
của thuật toán trộn.
Người ta tính được: T(n) = O(nlogn).
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Luyện tập 1 trang 44 Chuyên đề Tin học 11: Viết chương trình thực hiện công việc sau:
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.
