Hoạt động 1: Tìm hiểu cách đánh giá thời gian thực hiện chương trình
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. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.
Bài Làm:
Chương trình 1: Thời gian thực hiện chương trình là T1=T1(n)=2+n+1=n+3 (đơn vị thời gian)
Chương trình 2: Thời gian thực hiện chương trình là T2=T1(n)=2+n2+1=n2+3 (đơn vị thời gian)
Trong: Giải Tin học 11 định hướng KHMT Kết nối bài 24 Đánh giá độ phức tạp thời gian thuật toán
Câu hỏi. 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?
Câu hỏi 2. 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?
Câu hỏi . Tính độ phức tạp của các hàm thời gian sau:
a) Tính = 2n(n - 2) + 4.
b) Tính = $n^{3}$ + 5n - 3.
Câu hỏi. Á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ính = $n^{3}$ + nlogn + 2n + 1.
b) Tính = 3$n^{4}$ + 2$n^{2}$logn + 10.
Câu hỏi 1. 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)
Câu hỏi 2. 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)
Câu hỏi 1. 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
Câu hỏi 2. 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 nay.
Hoạt động 2: Tìm hiểu khái niệm độ phức tạp thời gian thuật toán
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.
Hoạt động 3: Tìm hiểu một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán
Đọ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.
Xem thêm các bài Giải tin học 11 định hướng Khoa học máy tính kết nối tri thức được biên soạn cho Học kì 1 & Học kì 2 theo mẫu chuẩn của Bộ Giáo dục theo sát chương trình Lớp 11 giúp bạn học tốt hơn.
Giải bài tập SGK, SBT, VBT và Trắc nghiệm các môn học Lớp 11, dưới đây là mục lục các bài giải bài tập sách giáo khoa và Đề thi chi tiết với câu hỏi bài tập, đề kiểm tra 15 phút, 45 phút (1 tiết), đề thi học kì 1 và 2 (đề kiểm tra học kì 1 và 2) các môn trong chương trình Lớp 11 giúp bạn học tốt hơn.
