Thông tin tài liệu:
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.
Nội dung trích xuất từ tài liệu:
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; i10