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

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

Câu 25.2 trang 77 SBT Tin học 11: 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]

Lời giải:

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).