Nội dung bài viết

    Xem thêm

    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 Hoạt động 3 trang 43 Chuyên đề Tin học 11 sách Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay nhất, chi tiết sẽ giúp học sinh dễ dàng trả lời các câu hỏi & làm bài tập.

    1 279 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Chuyên đề Tin học 11 Kết nối tri thức Bài 9: 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 các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

    Khởi động trang 40 Chuyên đề Tin học 11: Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp

    Hoạt động trang 40 Chuyên đề Tin học 11: Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn

    Câu hỏi 1 trang 41 Chuyên đề Tin học 11: Hãy thực hiện thao tác trộn hai dãy sau: B = 1, 4, 7; C = 2, 3, 6

    Câu hỏi 2 trang 41 Chuyên đề Tin học 11: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước tương tự trên

    Hoạt động 2 trang 41 Chuyên đề Tin học 11: Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn

    Câu hỏi 1 trang 43 Chuyên đề Tin học 11: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại dòng 6 có nhiều nhất là bao nhiêu bước lặp?

    Câu hỏi 2 trang 43 Chuyên đề Tin học 11: Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một phần tử

    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

    Câu hỏi 1 trang 44 Chuyên đề Tin học 11: Tính thời gian chạy của thuật toán sắp xếp trộn nếu A = [3, 1]

    Câu hỏi 2 trang 44 Chuyên đề Tin học 11: Mô tả thực hiện các bước của sắp xếp trộn với dãy A = [5, 1, 7, 4]. Trường hợp này T(4) sẽ được tính như thế nào?

    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:

    Luyện tập 2 trang 44 Chuyên đề Tin học 11: Viết lại chương trình hoàn chỉnh thực hiện sắp xếp trộn với dãy A

    Vận dụng 1 trang 44 Chuyên đề Tin học 11: Viết chương trình hoàn chỉnh nhập dãy số bất kì từ tệp văn bản

    Vận dụng 2 trang 44 Chuyên đề Tin học 11: Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước, cụ thể như sau.

    Xem thêm các bài giải Chuyên đề Tin học 11 sách Kết nối tri thức hay, chi tiết khác:

    Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị

    Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

    Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

    Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

    Bài 13: Kĩ thuật duyệt quay lui

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 279 20/08/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: