Để đánh giá độ phức tạp của thuật toán thường thì dùng BigO nhưng để hiểu rõ thì phải có 1 tí kiến thức về toán rời rạc :
- Nếu |f(x)| <= C|g(x)| khi và chỉ khi tồn tại x > k nào đó thì f(x) có bigO(g(x)).
Nếu đúng thì đáng lý phải làm cả 2 chiều cho cả bigOmega thì mới thực sự chính xác -> cận trên và dưới, nhưng trong thuật toán người ta thường chỉ dùng cận trên : bigO.
Ví dụ :
cho hàm số f(x) = x^2 + 2x + 1(1). Chứng minh nó là bigO(x^2).
Ta có : x^2 + 2x + 1 < x^2 + 2x^2 + x^2
<-> (1) < 4x^2 với mọi x > 1 ( chỗ k này có thể chọn bất kì để thỏa mãn bài toán là đủ, ở đây tui chọn k = 0 thì dấu = xảy ra vậy thôi).
Nhớ là >= nghĩa là > hoặc =, chứ không phải > và bằng.
Vậy rõ ràng là C = 4, k = 1 -> hàm đó là bigO(x^2)
Hay nói cách khác nó có độ phức tạp là x^2.
Cái đó là toán học h xét vào tin học xem :
Cứ mỗi 1 x thì có ứng với 0->n sự tính toán. Dùng kí hiệu Sima Tổng thì dễ dàng thấy nó là có độ phức tạp là x^2. Nhưng do tui type không được, nên bạn tự CM đi, nhớ là tổng 1 + 2 + 3... n = n(n + 1)/2C++ Code:
for(int x = 0; x < n; ++x) { for(int y = 0; y < n; ++y) { //tính toán gì đó } }
Cứ làm cho nhiều vào thì sẽ có cảm giác với độ phức tạp, nhưng nói chung cũng tùy bài. Thường thì các vòng lặp sẽ có độ phức tạp là bigO(n).