Độ phức tạp của thuật toán đồ họa

Chia sẻ: Vu Thi Thuy | Ngày: | Loại File: PDF | Số trang:17

Thêm vào BST

Báo xấu

157
lượt xem 25
download

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

Thời gian chạy của một thuật toán phụ thuộc vào cỡ của dữ liệu vào, trong các dữ liệu vào cùng một cỡ, thời gian chạy của thuật toán cũng thay đổi

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 của thuật toán đồ họa

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