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 25 Xác định độ phức tạp thời gian thuộc toán
Giải bài 25 Xác định độ phức tạp thời gian thuộc toán tin học lớp 11 kết nối tri thức. Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài.
Bài tập và hướng dẫn giải
Khởi động
Câu hỏi. Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?
Luyện tập
Câu hỏi 1. Xác định độ phức tạp của thuật toán sắp xếp nỗi bọt sau:
def BubbleSort(A):
n = len(A}
for i in range(n-1):
for" j in range(n-1-i):
for A[j] > A[j#1]:
A[j],A{fj+1] = A[3+1]1,A[3]
Câu hỏi 2. Cho biết hàm sau sẽ trả về giá trị là bao nhiêu? Xác định độ phức tạp thời gian O- lớn của chương trình.
Vận dụng
Câu hỏi 1. Giả sử rằng mỗi phép tính đơn được thực hiện trong micro giây (1 us = một phần triệu giây). Hãy xác định giá trị lớn nhất của n trong các thuật toán tìm kiếm tuần tự, sắp xếp chèn và sắp xếp chọn nếu thời gian thực thi các thuật toán là 1 giây, 1 phút và 1 giờ?
Câu hỏi 2. Hãy cho biết hàm sau thực hiện công việc gì? Xác định độ phức tạp thời gian của thuật toán.
