Giải SGK Tin học 11 KNTT Bài 25. Thực hành xác định độ phức tạp thời gian thuật toán có đáp án

Độ phức tạp của thuật toán sắp xếp nổi bọt là O(n$^{2}$)

T=O(n)+O(n$^{2}$)=O(n$^{2}$)Top of Form

Hàm "Mystery(n)" sẽ trả về giá trị là r.

Độ phức tạp thời gian của chương trình này là O(n$^{3}$)

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$^{6}$ us / phép tính) = 10$^{6}$

- 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 / phép tính) = 6 * 10$^{7}$

- 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 / phép tính) = 3.6 * 10$^{9}$

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$^{2}$

- 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$^{6}$us / phép tính)) =10$^{3}$

- 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$^{6}$us / phép tính)) = 6 * 10$^{4}$

- 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$^{6}$us / phép tính)) = 3.6 * 10$^{6}$

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$^{6}$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$^{6}$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$^{6}$us / phép tính)) = 3.6 * 10$^{6}$Bottom of Form

Công việc của hàm là thực hiện sắp xếp.

Độ phức tạp của thuật toán là O(n2)