Giải bài tập tin học lớp 11 định hướng KHMT kết nối tri thức bài 24 Đánh giá độ phức tạp thời gian thuật toán

Khởi động

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?

1. Đánh giá thời gian thực hiện chương trình

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.

Câu hỏi 1. 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. 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?

2. Phân tích độ phức tạp thời gian của thuật toán

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.

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.

3. Một số quy tắc thực hành tính độ phức tạp của 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.

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.

Luyện tập 

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)

Luyện tập

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)

Vận dụng

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

Vận dụng

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.