Bài giảng Khoa học máy tính - Bài 3: Độ phức tạp thuật toán - Lê Sỹ Vinh

Nội dung text: Bài giảng Khoa học máy tính - Bài 3: Độ phức tạp thuật toán - Lê Sỹ Vinh

1. ð phc tp thut toỏn Lờ S Vinh B mụn Khoa Hc Mỏy Tớnh – Khoa CNTT ði Hc Cụng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. 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ĩ năng 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” ???
3. ð 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 N phn t hay khụng? – Sp xp tăng dn dóy s gm N s – Bài toỏn ngưi bỏn hàng cn thăm N ủa ủim 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 N phn t hay khụng? – ði tưng nm ủu danh sach – ði tưng nm gia danh sach – ði tưng nm cui danh sỏch
4. ð phc tp thut toỏn 1. Thi gian chy trong trưng hp xu nht (worsecase 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 (bestcase running time) Thi gian chy ớt nht ca thut toỏn ủú trờn tt c cỏc d liu cựng c
5. ð 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). Mi phộp toỏn sơ cp ủưc thc hin trong mt khong thi gian c ủnh. – Quan tõm ủn tc ủ tăng ca hàm T(n) . – Vớ d: T(n) = 2n 2 + 3n + 10
6. Biu din thi gian chy bi kớ hiu O ðnh nghĩa . Gi s f(n) và g(n) là cỏc hàm thc khụng õm ca ủi s nguyờn khụng õm n. Ta núi “f( n) là ụ ln ca g(n)” và vit là f(n) = O( g(n) ) nu tn ti cỏc hng s dương c* và n 0 sao cho f(n) = n 0.
7. Biu din thi gian chy bi kớ hiu O Vớ d. Gi s f(n) = 5n 3 + 2n 2 + 13n + 6 , ta cú: f(n) = 5n 3 + 2n 2 + 13n + 6 <= 5n 3 + 2n 3 + 13n 3 + 6n 3 = 26n 3 f(n) = O(n 3) Tng quỏt nu f(n) là mt ủa thc bc k ca n: k k1 k f(n) = a kn + a k1n + + a 1n + a 0 thỡ f(n) = O(n )
8. Biu din thi gian chy bi kớ hiu O Ký hiu ụ ln Tờn gi O(1) hng O(logn) logarit O(n) tuyn tớnh O(nlogn) nlogn O(n 2) bỡnh phương O(n 3) lp phương O(2n) mũ
9. Thi gian chy ca cỏc lnh 1. Lnh gỏn X = Thi gian chy ca lnh gỏn bng thi gian thc hin biu thc 2. Lnh la chon if (ủiu kin) → T0(n) lnh 1 → T1(n) else lnh 2 → T2(n) Thi gian: T 0(n) + max (T 1(n), T 2(n))
10. Thi gian chy ca cỏc lnh 3. Lnh lp: for, while, dowhile Vớ d: X (n) ∑()T0 ()()n +Ti n i=1 X(n): S vũng lp T0(n): ðiu kin lp Ti(n): Thi gian thc hin vũng lp th i
11. Thi gian chy ca cỏc lnh 4. Phõn tớch cỏc hàm ủ quy
12. Vớ d 2 Thut toỏn to ra ma trn ủơn v A cp n. (1) for (i = 0 ; i < n ; i++) (2) for (j = 0 ; j < n ; j++) (3) A[i][j] = 0; (4) for (i = 0 ; i < n ; i++) (5) A[i][i] = 1; ð phc tp:
13. Vớ d 3 1) sum = 0; 2) for ( i = 0; i < n; i + +) 3) for ( j = i + 1; i < = n; j + +) 4) for ( k = 1; k < 10; k + +) 5) { sum = sum + i * j * k }; ð phc tp:
14. Vớ d 4 Phõn tớch ủ phc tp thut toỏn ca tt c cỏc phộp toỏn trờn kiu danh d liu danh sỏch ủưc cài ủt bng mng và danh sỏch liờn kt