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

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

0
355
lượt xem
105
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

Nội dung Text: Độ phức tạp thuật toán

  1. ð 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
  2. 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” ???
  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? – 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
  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 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
  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) ) n u t n t i các h ng s dương c* và n0 sao cho f(n) = n0.
  7. 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
  8. 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ũ
  9. 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))
  10. 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
  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 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:
  14. 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

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản