Với giải Vận dụng 1 trang 117 Tin học lớp 11 Kết nối tri thức chi tiết trong Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:

Giải bài tập Tin học lớp 11 Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Vận dụng 1 trang 117 Tin học 11: 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:

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

- Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự 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⁶ us / phép tính) = 10⁶

- 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⁶us / phép tính) = 6 * 10⁷

- 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⁶us / phép tính) = 3.6 * 10⁹

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

- Độ phức tạp thời gian của thuật toán sắp xếp chèn là O(10²

- 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 * (10⁶us / phép tính)) =10³

- 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) * (10⁶us / phép tính)) = 6 * 10⁴

- 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) * (10⁶us / phép tính)) = 3.6 * 10⁶

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

- Độ phức tạp thời gian của thuật toán sắp xếp chọn là O(n2)

- Giá trị lớn nhất của n là: n = sqrt(1 giây * (10⁶us / phép tính)) = 1000.

Thời gian thực thi là 1 phút:

Giá trị lớn nhất của n là: n = sqrt(1 phút * (60 giây / phút) * (10⁶us / phép tính)) = 60000.

Thời gian thực thi là 1 giờ:

Giá trị lớn nhất của n là: n = sqrt(1 giờ * (60 phút / giờ) * (60 giây / phút) * (10⁶us / phép tính)) = 3.6 * 10⁶