Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán

Chủ đề 6. Kĩ thuật lập trình – Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán – sách giáo khoa trang 115 lớp 11 Khoa học máy tính – Kết Nối Tri Thức, mời các em tham khảo cùng Bumbii.

Chủ đề 6. Kĩ thuật lập trình – Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán

Khởi động

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?

Lời giải:

Phân tích và đánh giá độ phức tạp thời gian giúp bạn hiểu rõ hiệu suất của thuật toán, làm cho quyết định chọn thuật toán trở nên thông minh hơn và cải thiện chất lượng của chương trình của bạn.

Luyện tập

Câu 1. Xác định độ phức tạp của thuật toán sắp xếp nổi bọt sau:

Lời giải:

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n²): T=O(n)+O(n²)=O(n²).

Câu 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.

Lời giải:

Hàm Mystery(n) sẽ trả về giá trị (n-2)(n-1)/2.

Độ phức tạp thời gian của chương trình này là O(n²), vì có ba vòng lặp lồng nhau và số lần lặp trong mỗi vòng lặp lớn tăng theo cấp số học.

Vận dụng

Câu 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ờ?

Lời giải:

– Thuật toán tìm kiếm tuần tự:

Độ phức tạp thời gian là O(n).

Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = 1 giây * (10^6 us/giây) = 106.

Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = 1 phút * 60 giây/phút * (10^6 us/giây) = 6 * 107.

Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = 1 giờ * 60 phút/giờ * 60 giây/phút * (10^6 us/giây) = 3.6 * 109.

– Thuật toán sắp xếp chèn:

Độ phức tạp thời gian là O(n2).

Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n = sqrt(1 giây * 106 us/giây) ≈ 1000.

Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n = sqrt(1 phút * 60 giây/phút * 106 us/giây) ≈ 7745.

Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n = sqrt(1 giờ * 60 phút/giờ * 60 giây/phút * 106 us/giây) ≈ 60000.

– Thuật toán sắp xếp chọn:

Độ phức tạp thời gian là O(n2).

Giá trị lớn nhất của n với thời gian thực thi là 1 giây: n ≈ 1000.

Giá trị lớn nhất của n với thời gian thực thi là 1 phút: n ≈ 7745.

Giá trị lớn nhất của n với thời gian thực thi là 1 giờ: n ≈ 60000.

Câu 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.

Lời giải:

Công việc của hàm này là sắp xếp một mảng A sử dụng thuật toán sắp xếp nổi bọt. Độ phức tạp thời gian của thuật toán này là O(n²), trong đó n là độ dài của mảng A.

Xem các bài giải khác: Giải bài tập SGK lớp 11 định hướng Khoa học máy tính – NXB Kết nối tri thức với cuộc sống

Thông tin liên hệ & mạng xã hội:
Website: https://bumbii.com/
Facebook: https://www.facebook.com/bumbiiapp
Pinterest: https://www.pinterest.com/bumbiitech