Độ phức tạp thuật toán

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:14

Thêm vào BST

Báo xấu

422
lượt xem 107
download

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

Tài liệu tham khảo về độ phức tạp thuật toán - môn Khoa học máy tính

Chủ đề:

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

Lưu

Nội dung Text: Độ 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 1. M t 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 – 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 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
ð 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
ð 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. – Quan tâm ñ n t c ñ tăng c a hàm T(n) . – 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)) i =1 0 i 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 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 }; ð ph c t p:
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