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

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

700
lượt xem 177
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Vinh B 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 nhau 1. M tv n 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 – 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á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? – 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ũng 2. 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 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 . 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 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) ) 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 O Ví 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 nh 1. 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 c 2. 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 nh 3. 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 nh 4. Phân tích các hàm quy
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:
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 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:
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. }
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