Cho biết thuật toán sau thực hiện công việc gì và hãy xác định độ phức tạp

thời gian của thuật toán.

1 def findMax(A):

2 maxVal = A[0]

Câu hỏi trong đề: Giải SBT 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 !!

Sách mới 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).

Quảng cáo

Trả lời:

Giải bởi Vietjack

Hàm trên thực hiện việc tìm phần tử lớn nhất của mảng A.

Gọi n là kích thước của mảng, T(n) là thời gian thực hiện của thuật toán. Thời gian chạy của thuật toán được phân tích như sau:

– Câu lệnh tại dòng 2 cần 1 đơn vị thời gian.

– Vòng lặp for tại dòng 3 biến i chạy từ 1 đến n − 1, nên vòng lặp có n – 1 bước lặp.

– Với mỗi bước lặp chương trình thực hiện 1 lệnh so sánh tại dòng 4 và 1 lệnh gán tại dòng 5 (nếu điều kiện thoả mãn).

– Lệnh trả về tại dòng 6 cần 1 đơn vị thời gian.

Tổng hợp lại chương trình trên có thời gian chạy là

T(n) = 2 + 2(n-1) = 2n = O(n).

Combo - Sổ tay kiên thức trọng tâm Toán, Lí, Hóa dành cho 2k7 VietJack

Sách - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia Hà Nội 2025 cho 2k7 VietJack

Sách Combo - Tuyển tập 30 đề thi đánh giá năng lực Đại học Quốc gia TP Hồ Chí Minh (2 cuốn) - 2025 cho 2k7 VietJack

Sách - Tuyển tập 15 đề thi Đánh giá tư duy Đại học Bách Khoa Hà Nội 2025 cho 2k7 VietJack

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Câu 1:

Xem đáp án » 13/07/2024 1,964

Câu 2:

Xem đáp án » 27/11/2023 1,311

Câu 3:

Xem đáp án » 27/11/2023 502

Câu 4:

Xem đáp án » 27/11/2023 339

Câu 5:

Xem đáp án » 13/07/2024 242

Câu 6:

Xem đáp án » 13/07/2024 240