Nội dung chính Tin học 11 theo định hướng khoa học máy tính Kết nối tri thức bài 24: Đánh giá độ phức tạp thời gian thuật toán

BÀI 24. ĐÁNH GIÁ ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

1. ĐÁNH GIÁ THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH

Cách đánh giá thời gian chạy chương trình được dựa trên một bộ khung các nguyên tắc dùng làm căn cứ để tính toán. Các nguyên tắc khung như sau:

1. Các phép toán đơn giản như phép tính số học + - */ phép lấy thương nguyên và số dư, các phép so sánh sẽ tinh là 1 đơn vị thời gian. 

2. Các phép toán lôgic cơ bản như AND, OR, NOT sẽ tính là 1 đơn vị thời gian. 

3. Các lệnh đơn như lệnh gán, lệnh in, đọc dữ liệu.... tính là 1 đơn vị thời gian.

4. Vòng lặp for hoặc while sẽ được tính thời gian bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp.

5. Lệnh if với nhiều trường hợp rẽ nhánh sẽ được tính thời gian bằng đơn vì thời gian lớn nhất của các lệnh nhánh.

→ Áp dụng các nguyên tắc tính khung thời gian trên chúng ta có thể tinh được gần chính xác thời gian thực hiện chương trình mà không cần cài đặt và chạy chương trình trên máy tính.

2. PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

- Kí hiệu O-lớn dùng để đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán tăng lên vô cùng.

- Định nghĩa O-lớn (big-O):

Cho f(n) và g(n) là hai hàm có đối số tự nhiên. Ta viết f(n) = O(g(n)) và nói f(n) có bậc O-lớn của g(n) nếu tồn tại hằng số c > 0 và số tự nhiên n0 ≥ 1 sao cho với mọi n ≥ n0 ta có f(n) ≤ c.g(n). Nếu f(n) là O-lớn của g(n) thì có thể viết f(n) = O(g(n)).

- Các thuật toán sẽ được đánh giá qua độ phức tạp của một số hàm chuẩn như:

O(1) - hằng số

O(logn) - logarit

O(n) - tuyến tính

O(nlogn) - tuyến tính logarit

O(n2) - bình phương

O(nk) - đa thức

O(an) - lũy thừa

O(n!) - giai thừa.

3. MỘT SỐ QUY TẮC THỰC HÀNH TÍNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN

- Quy tắc 1. Quy tắc cộng:

O(f(n) + g(n)) = O(max(f(n), g(n))).

→ Quy tắc này được áp dụng khi tính độ phức tạp thời gian cho hai chương trình được thực hiện nối tiếp nhau.

Ví dụ: T(n) = n2 + 2n = O(max(n2, 2n)) = O(n2).

- Quy tắc 2. Quy tắc nhân:

Phép nhân với hàm số:

O(f(n).g(n)) = O(f(n).O(gn))).

→ Quy tắc này áp dụng tính độ phức tạp cho chương trình có hai vòng lặp lồng nhau.

Ví dụ: T(n) = 10n2 = O(n2).

T(n) = 3n2 + nlogn = O(max(3n2, nlogn)) (Quy tắc cộng) = O(3n2) = O(n2) (Quy tắc nhân với hằng số).