Giáo trình Độ phức tạp thuật toán - Bài 3: Độ phức tạp thuật toán - Lê Sỹ Vinh

Nội dung text: Giáo trình Độ phức tạp thuật toán - Bài 3: Độ phức tạp thuật toán - Lê Sỹ Vinh

1. ph c t p thu t 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 v n liên quan n thu t toán 1. Mt v n ư c gi i quy t b i nhi u thu t toán khác nhau 2. i v i m t thu t toán: – ph c t p v không gian (dung l ư ng b nh s d ng) – ph c t p v th i gian ch y 3. ph c t p v th i gian ch y – K n ng l p trình – Ch ươ ng trình d ch – Tc th c hi n các phép toán trên máy tính – D li u vào “Th i gian ch y ch ơ ng trình : 10s” ???
3. ph c t p thu t toán 1. Th i gian ch y 1 thu t toán ph thu c vào c (size) c a d li u vào – Tìm xem 1 i t ư ng có trong danh sách N ph n t hay không? – Sp x p t ng d n dãy s g m N s – Bài toán ng ư i bán hàng c n th m N a im 2. Trong các d li u vào cùng m t c ( N), th i gian ch y c a thu t toán c ng thay i Ví d : Tìm xem 1 i t ư ng có trong danh sách N ph n t hay không? – i t ư ng n m u danh sach – i t ư ng n m gi a danh sach – i t ư ng n m cu i danh sách
4. ph c t p thu t toán 1. Th i gian ch y trong tr ư ng h p x u nh t (worse-case running time) Th i gian ch y l n nh t c a thu t toán ó trên t t c các d li u cùng c 2. Th i gian ch y trung bình Là trung bình c ng th i gian ch y trên t t c các b d li u cùng c . 3. Th i gian ch y trong tr ư ng h p t t nh t (best-case running time) Th i gian ch y ít nh t c a thu t toán ó trên t t c các d li u cùng c
5. ph c t p thu t toán Đánh giá th ời gian ch ạy thu ật toán: – T(n) = s l ư ng phép toán s ơ c p c n ph i th c hi n (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 ơ c p ư c th c hi n trong m t kho ng th i gian c nh. – Quan tâm n t c t ng c a hàm T(n) . – Ví d : T(n) = 2n 2 + 3n + 10
6. Bi u di n th i gian ch y b i kí hi u O Đị nh ngh ĩa. Gi s f(n) và g(n) là các hàm th c không âm c a i s nguyên không âm n. Ta nói “f( n) là ô l n c a g(n)” và vi t là f(n) = O( g(n) ) nu t n t i các h ng s d ươ ng c* và n 0 sao cho f(n) = n 0.
7. Bi u di n th i gian ch y b i kí hi u 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 n u f(n) là m t a th c b c k c a n: k k-1 k f(n) = a kn + a k-1n + + a 1n + a 0 thì f(n) = O(n )
8. Bi u di n th i gian ch y b i kí hi u O Ký hi u ô ln Tên gi O(1) hng O(logn) logarit O(n) tuy n tính O(nlogn) nlogn O(n 2) bình ph ươ ng O(n 3) lp ph ươ ng O(2n) m
9. Th i gian ch y c a các l nh 1. Lnh gán X = Th i gian ch y c a l nh gán b ng th i gian th c hi n bi u th c 2. Lnh l a chon if ( iu ki n) T0(n) lnh 1 T1(n) else lnh 2 T2(n) Th i gian: T 0(n) + max (T 1(n), T 2(n))
10. Th i gian ch y c a các l nh 3. Lnh l p: for, while, do-while Ví d : X (n) ∑()T0 ()()n +Ti n i=1 X(n): S vòng l p T0(n): iu ki n l p Ti(n): Th i gian th c hi n vòng l p th i
11. Th i gian ch y c a các l nh 4. Phân tích các hàm quy
12. Ví d 2 Thu t toán t o ra ma tr n ơ n v A c p 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; Độ ph ức t ạp:
13. Ví d 2’ Thu t toán t o ra ma tr n ơ n v A c p n. (1) for (i = 0 ; i < n ; i++) (2) for (j = 0 ; j < n ; j++) (3) if (i == j) (4) A[i][j] = 1; (5) Else (6) A[i][j] = 0; Độ ph ức t ạp:
14. Ví d 3 1) sum = 0; 2) for ( i = 0; i < n; i + +) 3) for ( j = i + 1; j < = n; j + +) 4) for ( k = 1; k < 10; k + +) 5) sum = sum + i * j * k ; Độ ph ức t ạp:
15. Ví d 3’ 1) sum = 0; 2) for ( i = 0; i < n; i + +) 3) for ( j = i + 1; j < = n; j + +) 4) for ( k = 1; k < m; k + +) { 5) x = 2*y; 6) sum = sum + i * j * k ; 7) } Độ ph ức t ạp:
16. 3’’ 1. for (i = 0; I < n; I ++) 2. for (j = 0; j < m; j ++) { 3. int x = 0; 4. for (k = 0; k < n; k ++) 5. x = x + k; 6. for (k = 0; k < m; k++) 7. x = x +k; 8. }
17. Ví d ụ 4 Phân tích ph c t p thu t toán c a t t c các phép toán trên ki u danh d li u danh sách ư c cài t b ng m ng và danh sách liên k t