Bài 25.2. 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.
Bài Làm:
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 thỏa 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)
