Tin học 11 Bài 24: Đánh giá độ phức tạp thời gian thuật toán Giải Tin học 11 Định hướng Khoa học máy tính Kết nối tri thức

Giải bài tập SGK Tin học 11 trang 111→114 sách Kết nối tri thức với cuộc sống giúp các em học sinh lớp 11 xem gợi ý giải các câu hỏi Bài 24: Đánh giá độ phức tạp thời gian thuật toán thuộc Chủ đề 6: Kỹ thuật lập trình.

Soạn Tin học 11 Kết nối tri thức Bài 24 giúp các bạn học sinh nắm được kiến thức biết cách đánh giá mức độ phức tạp thời gian thuật toán. Đồng thời qua tài liệu này giúp giáo viên nhanh chóng xây dựng hoàn thiện giáo án dạy học của mình.

Trả lời Nội dung bài học Tin 11 Bài 24

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

Hoạt động 1: 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.

Gợi ý đáp án

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+n²+1=n²+3 (đơn vị thời gian)

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?

Gợi ý đáp án

a) T1=1+n//3=1+1000000//3 đơn vị thời gian

b) T2=1+1+(n//3)=2+1000000//3 đơ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?

Gợi ý đáp án

Sai. Trong một chương trình máy tính, có thể có nhiều phép toán tích cực (positive operations), cũng như các phép toán khác nhau, chẳng hạn phép toán cộng, trừ, nhân, chia, so sánh, gán giá trị, và các phép toán logic, v.v… Các phép toán tích cực là các phép toán thực hiện các tính chất tích cực của chương trình, như tính toán dữ liệu, xử lý logic, và đưa ra kết quả mong đợi.

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

Hoạt động 2: 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.

Gợi ý đáp án

Thuật toán là một chuỗi các bước được thiết kế để giải quyết một vấn đề cụ thể. Một trong những yếu tố quan trọng để đánh giá hiệu suất của một thuật toán là độ phức tạp thời gian, tức là thời gian mà thuật toán mất để thực thi dựa trên kích thước đầu vào của vấn đề. Phân loại thuật toán dựa trên độ phức tạp thời gian là một phương pháp được sử dụng phổ biến để đánh giá và so sánh hiệu suất của các thuật toán khác nhau. Dưới đây là một số phân loại chính dựa trên độ phức tạp thời gian của thuật toán:

-O(1) (độ phức tạp thời gian hằng số): Đây là loại thuật toán có thời gian thực thi không thay đổi theo kích thước đầu vào. Thời gian thực thi của thuật toán này là cố định, vì vậy độ phức tạp thời gian là hằng số. Ví dụ: Truy cập vào phần tử trong mảng có kích thước cố định.

-O(log n) (độ phức tạp thời gian logarithmic): Đây là loại thuật toán có thời gian thực thi tăng theo logarit của kích thước đầu vào. Thuật toán này thường được sử dụng trong các bài toán tìm kiếm nhị phân, các thuật toán chia để trị, hoặc các thuật toán sắp xếp hiệu quả như QuickSort hoặc MergeSort.

-O(n) (độ phức tạp thời gian tuyến tính): Đây là loại thuật toán có thời gian thực thi tăng tỷ lệ trực tiếp với kích thước đầu vào. Ví dụ: Duyệt qua từng phần tử trong mảng một lần.

-O(n^2) (độ phức tạp thời gian bậc hai): Đây là loại thuật toán có thời gian thực thi tăng theo bình phương của kích thước đầu vào. Ví dụ: Thuật toán sắp xếp Bubble Sort, các thuật toán tìm kiếm không hiệu quả như Linear Search trong một mảng lồng nhau.

-O(n^k) (độ phức tạp thời gian bậc k): Đây là loại thuật toán có thời gian thực thi tăng theo lũy thừa của kích thước đầu

Câu hỏi: 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) = n³ + 5n – 3.

Gợi ý đáp án

a) T(n) = 2n(n – 2) + 4 = 2n² – 4n + 4 = O(n²)

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

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 Đọ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.

Gợi ý đáp án

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  Á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) = n³ + nlogn + 2n + 1.

b) T(n) = 3n⁴ + 2n²logn + 10.

Gợi ý đáp án

a)T(n) = O(n³)

a)T(n) = O(n⁴)

Luyện tập Tin học 11 Bài 24

Luyện tập 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 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 Tin học 11 Bài 24

Vận dụng 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 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 này.