Khoa học máy tính - Độ phức tạp thuật toán

Tham khảo tài liệu khoa học máy tính - độ phức tạp thuật toán, công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Khoa học máy tính - Độ phức tạp thuật toán ph c t p thu t toán Lê S VinhB môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhioi@yahoo.com Các v n liên quan n thu t toán ư c gi i quy t b i nhi u thu t toán khác nhau1. M tv n2. 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 – T c 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” ??? ph c t p thu t toán1. 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? – S p 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 i m – 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ũng2.2. 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 – ph c t p thu t toán Th i gian ch y trong trư ng h p x u nh t (worse-case running time)1. 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 c2. 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 . Th i gian ch y trong trư ng h p t t nh t (best-case running time)3. 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 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 h c, 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. tăng c a hàm T(n) . Quan tâm nt c – Ví d : – T(n) = 2n2 + 3n + 10 Bi u di n th i gian ch y b i kí hi u Onh 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) ) n u t n t i các h ng s dương c* và n0 sao cho f(n) = n0. Bi u di n th i gian ch y b i kí hi u OVí d . Gi s f(n) = 5n3 + 2n2 + 13n + 6 , ta có: f(n) = 5n3 + 2n2 + 13n + 6 Bi u di n th i gian ch y b i kí hi u O Ký hi u ô l n Tên g i O(1) h ng O(logn) logarit O(n) tuy n tính O(nlogn) nlogn O(n2) bình phương O(n3) l p phương O(2n) mũ Th i gian ch y c a các l nh1. L nh 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 c2. L nh l a chon → if ( i u ki n) T0(n) → l nh 1 T1(n) else → l nh 2 T2(n) Th i gian: T0(n) + max (T1(n), T2(n)) Th i gian ch y c a các l nh3. L nh l p: for, while, do-while Ví d : X (n) ∑ (T (n ) + T (n )) 0 i i =1 X(n): S vòng l p T0(n): i u ki n l p Ti(n): Th i gian th c hi n vòng l p th i Th i gian ch y c a các l nh4. Phân tích các hàm quy Ví d 2Thu 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: 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: Ví d 31) 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: 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: 3’’1. for (i = 0; I < n; I ++)2. for (j = 0; j < m; j ++) {3. int x = 0;4.4. for (k = 0; k < n; k ++)5. x = x + k;6. for (k = 0; k < m; k++)7. x = x +k;8. ...