Nội dung bài viết

    Xem thêm

    Giải Tin học 11 trang 114 Kết nối tri thức

    Với Giải Tin học 11 trang 114 Bài 24: Đánh giá độ phức tạp thời gian thuật toán sách Kết nối tri thức giúp học sinh dễ dàng làm bài tập Tin học 11.

    1 182 07/06/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Giải Tin học 11 trang 114 Kết nối tri thứ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:

    a) T(n) = 2n(n - 2) + 4.

    b) T(n) = n3 + 5n - 3.

    Lời giải:

    a) T(n) = 2n(n - 2) + 4 = 2n2 - 4n + 4 = O(n2)

    b) T(n) = n3 + 5n – 3 = O(n3)

    3. Một số quy tắc thực hành tính độ phức tạp thời gian thuật toán

    Hoạt động 3 trang 114 Tin học 11: Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.

    Lời giải:

    QT1. Quy tắc cộng: O(f(n)+g(n))=O(max(f(n),g(n)))

    QT2. Quy tắc nhân:

    - Với hằng sô: O(C.f(n))=O(f(n))

    - Với hàm số: O(f(n).g(n))=O(f(n)).O(g(n))

    Câu hỏi trang 114 Tin học 11: Áp dụng các quy tác trên để tính độ phức tạp của các hàm thời gian sau:

    a) T(n) = n3 + nlogn + 2n + 1.

    b) T(n) = 3n4 + 2n2logn + 10.

    Lời giải:

    a)T(n) = O(n3)

    a)T(n) = O(n4)

    Luyện tập

    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:

    n = 1000

    s = 0

    for i in range (n);

       s = s + i*(i+1)

    print (s)

    Lời giải:

    Chương trình trên tính tổng các giá trị i*(i+1) trong khoảng từ 0 đến n-1 và lưu kết quả vào biến s. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng for và các phép toán trong vòng lặp.

    Vòng for: Vòng lặp này chạy từ 0 đến n-1, với n là 1.000. Vậy số lần lặp là n, hay 1.000 lần.

    Các phép toán trong vòng lặp:

    Phép gán s = s + i*(i+1): Đây là phép gán giá trị vào biến s, có độ phức tạp là O(1).

    Phép toán i*(i+1): Đây là phép nhân và cộng, có độ phức tạp là O(1).

    Vậy tổng độ phức tạp thời gian của chương trình là O(n), hay O(1.000)

    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:

    n = 1000

    sum = 0

    i = 1

    while i <n;

      i = i*2

      sum = sum + 1

    print (sum)

    Lời giải:

    Chương trình trên tính số lần lặp cần thiết để i lớn hơn n bằng cách nhân i với 2 trong mỗi lần lặp, sau đó tăng biến sum lên 1. Để xác định độ phức tạp thời gian của chương trình này, ta cần xem xét số lần lặp của vòng while và các phép toán trong vòng lặp.

    Vòng while: Vòng lặp này chạy cho đến khi i >= n, và giá trị ban đầu của i là 1. Trong mỗi lần lặp, i được nhân với 2, vậy số lần lặp là log2(n) (vì sau mỗi lần nhân i với 2, giá trị của i sẽ gấp đôi). Ví dụ, nếu n = 1000 thì số lần lặp là log2(1000) ≈ 10.

    Các phép toán trong vòng lặp:

    Phép gán i = i * 2: Đây là phép nhân, có độ phức tạp là O(1).

    Phép gán sum = sum + 1: Đây là phép gán giá trị vào biến sum, có độ phức tạp là O(1).

    Vậy tổng độ phức tạp thời gian của chương trình là O(log n), hay O(log2(1000)) ≈ O(10)

    Vận dụng

    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ố phần 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ử.

    Vận dụng 2 trang 114 Tin học 11: Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.

    Lời giải:

    *Chương trình 1:

    from collections import Counter

    import time

    n = 1000

    c = 0

    # Ghi lại thời điểm bắt đầu

    start_time = time.time()

    for k in range(n):

      c = c + 1

    # Ghi lại thời điểm kết thúc

    end_time = time.time()

    # Tính thời gian hoàn thành

    elapsed_time = end_time - start_time

    # Sử dụng hàm Counter để đếm số lần lặp

    counter = Counter(range(n))

    # In số lần lặp

    print("Số lần lặp: {}".format(counter))

    # In thời gian thực thi

    print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

    *Chương trình 2:

    import time

    n = 1000

    c = 0

    # Ghi lại thời điểm bắt đầu

    start_time = time.perf_counter()

    for k in range(n):

     for j in range(n):

      c = c + 1

    # Ghi lại thời điểm kết thúc

    end_time = time.perf_counter()

    # Tính thời gian hoàn thành

    elapsed_time = end_time - start_time

    # In số lần lặp

    print("Số lần lặp: {}".format(c))

    # In thời gian thực thi

    print("Thời gian thực thi của chương trình: {:.6f} giây".format(elapsed_time))

    →Sự khác biệt độ phức tạp thời gian của 2 chương trình trên:

    Độ phức tạp thời gian của chương trình 1 là O(1), còn độ phức tạp thời gian của chương trình 2 là O(n2).

    Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

    Giải Tin học 11 trang 113

    Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

    Khởi động trang 111 Tin học 11: Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?

    Hoạt động 1 trang 112 Tin học 11: Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2

    Câu hỏi 1 trang 113 Tin học 11: Các lệnh và đoạn chương tình sau cần chạy trong bao nhiêu đơn vị thời gian?

    Câu hỏi 2 trang 113 Tin học 11: Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?

    Hoạt động 2 trang 113 Tin học 11: Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.

    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:

    Hoạt động 3 trang 114 Tin học 11: Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.

    Câu hỏi trang 114 Tin học 11: Áp dụng các quy tác trên để 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:

    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.

    Vận dụng 2 trang 114 Tin học 11: Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính

    Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:

    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

    Bài 28: Thiết kế chương trình theo mô đun

    Bài 29: Thực hành thiết kế chương trình theo mô đun

    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 182 07/06/2023
    Trang trước
    Chia sẻ
    Trang sau  

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