xin hỏi về đánh giá độ phức tạp thuật toán

[xiah1488]

Để đánh giá độ phức tạp của thuật toán nguòi ta dùng kí pháp O,tôi vẫn chưa hiểu về cái này,các bạn giải thích dum tôi đi

[rox_rook]

Để đá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 :

 for(int x = 0; x < n; ++x)    {        for(int y = 0; y < n; ++y)        {            //tính toán gì đó         }    }

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

[Tarzan]

Cái đó là đánh giá chung chung thôi, còn độ phức tạp còn phải hiểu theo cả độ phức tạp về thời gian và không gian nhớ nữa.

Không gian nhớ ngày càng rẻ, nên độ phức tạp thời gian được nhắc đến dưới dạng 'số lượng phép toán bit cần phải thực hiện'.

Để tính được nó, cần có thuật toán chi tiết chứ nói nôm na là vòng lặp có O(n) thì cũng đúng một phần.

Bác rox_rook viết bài này tốt quá. Không vote được nhỉ.