 phc tp thut toán
Lê SVinh
Bmôn Khoa Hc Máy Tính – Khoa CNTT
i Hc Công Ngh-HQGHN
Email: vinhioi@yahoo.com
Các vn  liên quan n thut toán
1. Mt vn  ưc gii quyt bi nhiu thut toán khác nhau
2. i vi mt thut toán:
– phc tp v không gian (dung lưng b nh s dng)
– phc tp v thi gian chy
3.  phc tp v thi gian chy
–K nng lp trình
–Chương trình dch
–Tc  thc hin các phép toán trên máy tính
–D liu vào
“Thi gian chy chơng trình : 10s” ???
 phc tp thut toán
1. Thi gian chy 1 thut toán ph thuc vào c (size) ca d liu vào
–Tìm xem 1 i tưng có trong danh sách Nphn t hay không?
–Sp xp tng dn dãy s g m Ns
–Bài toán ngưi bán hàng cn thm N a i!m
2.
Trong các d liu vào cùng mt c (
N
), thi gian chy ca thut toán c"ng
2.
Trong các d liu vào cùng mt c (
N
), thi gian chy ca thut toán c"ng
thay #i
Ví d: Tìm xem 1 i tưng có trong danh sách Nphn t hay không?
–i tưng n$m u danh sach
–i tưng n$m gia danh sach
–i tưng n$m cui danh sách
 phc tp thut toán
1. Thi gian chy trong trưng hp xu nht (worse-case running time)
Thi gian chy ln nht ca thut toán ó trên tt c các d liu cùng c
2. Thi gian chy trung bình
Là trung bình cng thi gian chy trên tt c các b d liu cùng c.
3. Thi gian chy trong trưng hp tt nht (best-case running time)
Thi gian chy ít nht ca thut toán ó trên tt c các d liu cùng c
 phc tp thut toán
ánh giá thi gian chy thut toán:
–T(n) = s lưng phép toán sơ cp cn phi thc hin (phép toán s
hc, phép toán logic, phép toán so sánh). M%i phép toán sơ cp
ưc thc hin trong mt khong thi gian c nh.
–Quan tâm n tc  tng ca hàm T(n) .
–Ví d:
T(n) = 2n2+ 3n + 10