Chương 10-Phân tích thuật toán

Chia sẻ: Mvnc Bgfhf | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

70
lượt xem 6
download

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

Hầu hết các bài toán đều có nhiều thuật toán khác nhau để giải quyết chúng. Như vậy, làm thế nào để chọn được sự cài đặt tốt nhất? Đây là một lĩnh vực được phát triển tốt trong nghiên cứu về 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: Chương 10-Phân tích thuật toán

NH P MÔN L P TRÌNH CHƯƠNG 10 PHÂN TÍCH THU T TOÁN 1
N I DUNG 1 ánh giá th i gian th c hi n thu t toán 2 ph c t p c a thu t toán 3 Phương pháp tính ph c t p 5 2 CTDL1- Nguy n H u Th
1. Phân tích thu t toán − ánh giá chi phí và th i gian th c hi n thu t toán. − Th i gian tính toán c a thu t toán => ph thu c kích thư c u vào (size of input). − N u g i n là kích thư c d li u ưa vào => th i gian th c hi n c a m t thu t toán có th bi u di n như m t hàm c a n: T(n). − Ph n c ng máy tính, ngôn ng , chương trình d ch u nh hư ng t i th i gian th c hi n. Ví d : N u như th i gian th c hi n m t thu t toán T1(n) = n2 Và th i gian th c hi n c a m t thu t toán khác T2(n) = 100n => Khi n l n, th i gian th c hi n c a thu t toán T2 nhanh hơn thu t toán T1. 3 CTDL1- Nguy n H u Th
2. ph c t p c a thu t toán − Cho m t hàm T(n), T(n) g i là có ph c t p f(n) n u t n t i các h ng C • sao cho T(n) ≤ C*f(n) T c là T(n) có t su t tăng là f(n) • kí hi u: O(f(n)) ( c là “ô c a f(n)”). Chú ý: O(C.f(n))=O(f(n)) v i C là h ng s . Ð c bi t: O(C)=O(1) 4 CTDL1- Nguy n H u Th
2. ph c t p c a thu t toán − B ng các c p th i gian th c hi n thu t toán: − Các hàm như log2n, n, nlog2n, n2, n3 g i là các hàm a th c. − Gi i thu t v i th i gian th c hi n có c p hàm a th c thư ng ch p nh n ư c. − Các hàm như 2n, n!, nn ư c g i là hàm mũ => t c r t ch m. 5 CTDL1- Nguy n H u Th
3. Phương pháp tính ph c t p − Phương pháp tính ph c t p (th i gian th c hi n) c a: Chương trình không g i chương trình con. Chương trình có g i chương trình con không quy. Chương trình quy − Hai qui t c quan tr ng: Qui t c c ng: N u T1(n) và T2(n) là th i gian th c hi n c a hai o n chương trình P1 và P2 • T1(n) = O(f(n)), • T2(n) = O(g(n)) • => th i gian th c hi n n i ti p nhau là T(n) = O(max(f(n),g(n))). Qui t c nhân: N u T1(n) và T2(n) là th i gian th c hi n c a hai o n chương trình P1và P2 • T1(n) = O(f(n)), • T2(n) = O(g(n)) • => th i gian th c hi n là T(n) = O(f(n)*g(n)). 6 CTDL1- Nguy n H u Th
3. Phương pháp tính ph c t p Phân tích m t chương trình không có chương trình con: Th i gian th c hi n c a m i l nh gán, Read, Write là O(1) Th i gian th c hi n c a m t chu i tu n t các l nh ư c xác nh b ng qui t c c ng. • => th i gian thi hành m t l nh lâu nh t trong chu i các l nh. Th i gian th c hi n c u trúc IF-ELSE: th i gian l n nh t th c hi n l nh sau IF ho c sau ELSE và th i gian ki m tra i u ki n. Thư ng th i gian ki m tra i u ki n là O(1). Th i gian th c hi n vòng l p: t ng (trên t t c các l n l p) th i gian th c hi n thân vòng l p. N u th i gian th c hi n thân vòng l p không i: • th i gian th c hi n vòng l p = (s l n l p) * (th i gian th c hi n thân vòng l p). 7 CTDL1- Nguy n H u Th
3. Phương pháp tính ph c t p Ví d : th t c s p x p “n i b t” void BubbleSort(int a[], int n) − Toàn b chương trình ch g m: { int i,j,temp; /*1*/ for(i= 0; i=i ; j--) l ng trong l nh {1} là l nh l p {2} /*3*/ if (a[j] < a[j-1]){ l ng trong l nh {2} là l nh {3} /*4*/ temp=a[j-1]; /*5*/ a[j-1] = a[j]; l ng trong l nh {3} là 3 l nh n i ti p nhau {4}, {5} và {6}. /*6*/ a[j] = temp; } − Chúng ta s ti n hành tính ph c t p } theo th t t trong ra. − Trư c h t, c ba l nh gán {4}, {5} và {6} u t n O(1) th i gian, so sánh a[j-1]> a[j] cũng t n O(1) th i gian, do ó l nh {3} t n O(1) th i gian. − Vòng l p {2} th c hi n (n-i) l n, m i l n O(1) => vòng l p {2} t n O((n-i).1) = O(n-i). − Vòng l p {1} có i ch y t 0 n n-2 nên th i gian th c hi n c a vòng l p {1} và cũng là ph c t p c a gi i thu t là: 8 CTDL1- Nguy n H u Th
Bài t p: tính ph c t p void SelectionSort(int a[],int N ) { int min; // ch s ph n t nh nh t trong dãy hi n hành for (int i=0; i
10