2.Trình bày KN độ phức tạp thuật toán,Ttoán đơn định đa thức,không đơn đinh đa thức,các quy tắc đánh giá độ phức tạp thuật toán.

-KN : TToán T có độ phức tạp bằng độ phức tạp về thời gian T(n) (n là kích thước Dl đầu vào).T(n) có độ phức tạp là O(f(n)) khi và chỉ khi tồn tại hằng số c,n0 sao cho :

T(n)<= c.f(n) với mọi n>=n0

-Thuật toán có độ phức tạp đa thức thì gọi là thuật toán đa thức.

-các thuật toán có độ phức tạp hàm mũ thì gọi là thuật toán trên đa thức.

-Thuật toán đơn định là trong mọi ttoán chí trả về 1kq.

-Thuật toán 0 đơn định là có ít nhất 1 thuật toán trả về 2kq trở lên.

=> TT đơn định đa thức là thuật toán có độ phức tạp đa thức và tt chỉ trả về 1kq

=>TT o đơn định da thức là thuật toán có độ phức tạp đa thức và có ít nhất một thuật toàn trả về 2kq trở lên.