Bài học cùng chủ đề
Lí thuyết về Đánh giá độ phức tạp của thuật toán SVIP
1. Đánh giá thời gian thực hiện của chương trình
Khung nguyên tắc đánh giá
Thời gian thực hiện của chương trình đang xét bằng:
1. Một đơn vị thời gian: phép so sánh, logic cơ bản, tính số học, lệnh đơn,...
2. Tổng đơn vị thời gian thực hiện mỗi lần lặp: vòng for, while.
3. Đơn vị thời gian lớn nhất của các lệnh rẽ nhánh: lệnh if nhiều nhánh rẽ.
2. Phân tích độ phức tạp thời gian của thuật toán
Một bài toán có thể được giải bằng nhiều thuật toán, mỗi thuật toán sẽ có hàm thời gian \(T(n)\) khác nhau → phân tích bậc của hàm \(T(n)\) để lựa chọn thuật toán phù hợp nhất.
Cho \(f\left(n\right)\) và \(g\left(n\right)\) là hai hàm có đối số tự nhiên. Ta viết \(f\left(n\right)=O\left(g\left(n\right)\right)\) và nói \(f\left(n\right)\) có bậc O-lớn của \(g\left(n\right)\) nếu tồn tại hằng số \(c>0\) và số tự nhiên \(n_0\ge1\) sao cho với mọi \(n=n_0\) ta có \(f\left(n\right)\le c.g\left(n\right)\). Nếu \(f\left(n\right)\) là O-lớn của \(g\left(n\right)\) thì có thể viết: \(f\left(n\right)=O\left(g\left(n\right)\right)\).
❓Ví dụ. Xác định độ phức tạp thời gian của hàm thời gian \(T\left(n\right)=n^2+3\).
Giải
Chọn \(c=2,n_0=2\). Khi đó \(n\ge n_0\), ta có:
\(T\left(n\right)=n^2+3< n^2+n_0^2\le n^2+n^2=2n^2=c.n^2\).
Vậy suy ra \(T\left(n\right)=O\left(n^2\right)\) - độ phức tạp thời gian hàm bình phương.
3. Quy tắc thực hành tính độ phức tạp thời gian của thuật toán
❓ Ví dụ. Hãy áp dụng quy tắc cộng cho một số hàm thời gian sau:
a) \(T\left(n\right)=10n+logn+3.\)
b) \(T\left(n\right)=5n^2+nlogn.\)
Giải
a) \(O\left(max\left(10n,logn,3\right)\right)=O\left(n\right)\)
b) \(O\left(max\left(5n^2,nlogn\right)\right)=O\left(n^2\right)\)
Phép nhân hằng số: \(O\left(C\cdot f\left(n\right)\right)=O\left(f\left(n\right)\right)\), với \(C\) là hằng số.
Phép nhân với hàm số: \(O\left(f\left(n\right)\cdot g\left(n\right)\right)=O\left(f\left(n\right)\right)\cdot O\left(g\left(n\right)\right)\). Sử dụng khi chương trình có hai vòng lặp lồng nhau.
❓ Ví dụ. Hãy áp dụng quy tắc nhân cho hàm \(T\left(n\right)=10n+nlogn+3.\)
Giải
\(T\left(n\right)=10n+nlogn+3=O\left(max\left(3n^2,nlogn\right)\right)=O\left(3n^2\right)=O\left(n^2\right)\)
