Giới thiệu thuật toán và đánh giá thuật toán
Thuật toán: Thuật toán :
Tập các chỉ thị với cấu trúc điều khiển mà dựa vào đó các chỉ thị được tiến hành. vào đó các chỉ thị được tiến hành.
Tính chất :
Rõ ràng
Đúng
Dừng
40 trang |
Chia sẻ: haohao89 | Lượt xem: 2104 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật: Giới thiệu thuật toán và đánh giá thuật toán, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
Lý thuyết
Phần 1 (Chương 1, 2, 9, 10)
Giới thiệu thuật toán và đánh giá thuật toán
Hàm mũ hàm logarit ,
Tính đệ quy và thuật toán đệ quy
Vũ Anh Dũng - Khoa CNTT 2
Thuật toán
Giới thiệu thuật toán và đánh giá thuật toán
Thuật toán :
Tập các chỉ thị với cấu trúc điều khiển mà dựa
vào đó các chỉ thị được tiến hành.
Tính chất :
Rõ ràng
Đúng
Dừng
Vũ Anh Dũng - Khoa CNTT 3
Thuật toán
Giới thiệu thuật toán và đánh giá thuật toán
Xét bài toán tìm phần tử lớn thứ k trong mảng
Sắp xếp giảm dần toàn mảng
Sắp xếp k phần tử đầu tiên và chèn dần
Chương 7 giới thiệu 1 thuật toán đủ tốt
Xét bài toán trò chơi ô chữ
Vũ Anh Dũng - Khoa CNTT 4
Thuật toán
¾ Có thể đánh giá dựa trên thời gian chạy
¾ Làm thế nào để đánh giá thời gian chạy của
một chương trình?
¾ Đánh giá thời gian chạy không thực sự dựa
trên mã lệnh của chúng.
Vũ Anh Dũng - Khoa CNTT 5
Một số hàm toán học
Hàm mũ
Hàm logarit
Chuỗi số
ồ Phép đ ng dư
a mod b
Vũ Anh Dũng - Khoa CNTT 6
Chứng minh
Quy nạp
P(n) = 1+2+3+ +n = n(n+1)/2 …..
Phản chứng
ớ ố ê d bấ kì ó íV i 16 s nguy n ương t ta c t
nhất hiệu của 2 số trong đó chia hết
h 15c o
Vũ Anh Dũng - Khoa CNTT 7
Đệ quy và giải thuật đệ quy
Khái niệm : Ta nói một đối tượng là đệ quy nếu nó
bao gồm chính nó như một bộ phận hoặc nó được
định nghĩa dưới dạng chính nó.
Ví dụ :
người giàu, màn hình TV.
Số tự nhiên :
1 là ố t hiê s ự n n
X là số tự nhiên nếu X-1 là số tự nhiên
Giai thừa
Vũ Anh Dũng - Khoa CNTT 8
Ví dụ hàm sau : 2)1(2)( xxfxf +−=
Đệ quy và giải thuật đệ quy
Giải thuật đệ quy và thủ tục đệ quy :
Nếu lời giải của bài toán T được thực hiện bằng lời giải
của bài toán T’ có dạng giống T, thì đó là một lời giải
đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là
giải thuật đệ quy Điểm chú ý là T’ phải “nhỏ hơn” T . .
¾ Trường hợp cơ sở
¾ Tạo tiến trình
ế Đệ quy trực ti p (directly rescursive) : Chứa lời gọi trực
tiếp đến chính nó.
Đệ quy gián tiếp (indirectly rescursive) : Chứa lời gọi
Vũ Anh Dũng - Khoa CNTT 9
đến một hàm khác, mà hàm khác lại gọi đến nó.
Đệ quy và giải thuật đệ quy
Thiết kế giải thuật đệ quy :
Hàm N!
Hàm Fibonaci
F(n) = 1 nếu n<=2
F(n) = F(n-2) + F(n-1) if n>2
Viết một số theo thứ tự ngược lại. Ví dụ :
2893 được viết lại là 3982
Vũ Anh Dũng - Khoa CNTT 10
Đệ quy và giải thuật đệ quy
1 void printOut( int n ) // In số n
không âm
2 {
3 printDigit( n % 10 );
4 if( n >= 10 )
5 printOut( n / 10 );
6
7 }
Vũ Anh Dũng - Khoa CNTT 11
Đệ quy và giải thuật đệ quy *
Bài toán “Tháp Hà Nội”
Phát biểu bài toán :
Có 3 cọc, cần chuyển đĩa từ cọc A sang cọc C
Cọc trung gian B
Mỗi lần chỉ được chuyển 1 đĩa
Không bao giờ có trường hợp đĩa to ở trên đĩa nhỏ
Tất cả các đĩa có kĩch cỡ khác nhau
Vũ Anh Dũng - Khoa CNTT 12
Đệ quy và giải thuật đệ quy *
Đệ quy quay lui (back tracking):
Bài toán tổ hợp chỉnh hợp ,
Bài toán người mua hàng
Bài toán tám quân hậu
Vũ Anh Dũng - Khoa CNTT 13
Đánh giá thuật toán
Thuật toán đòi hỏi bao nhiêu tài nguyên về
không gian và thời gian?
Làm sao để ước lượng thời gian chạy của
một chương trình?
Vũ Anh Dũng - Khoa CNTT 14
Các định nghĩa
Định nghĩa 2.1.
T(N) = O(f(N)) nếu có các hằng số dương c
và n0 sao cho T(N) ≤ cf(N) khi N ≥ n0.
Định nghĩa 2 2 . .
T(N) = Ω(g(N)) nếu có các hằng số dương c
à h ( ) ( ) khv n0 sao c o T N ≥ cg N i N ≥ n0.
Vũ Anh Dũng - Khoa CNTT 15
T(N) là đại lượng tổng quát của tài nguyên cần dùng
Các định nghĩa
Định nghĩa 2.3.
T(N) = Ө (h(N)) nếu và chỉ nếu T(N) =
O(h(N)) và T(N) = Ω(h(N)).
Định nghĩa 2 4 . .
T(N) = o(p(N)) nếu với mọi hằng số c tồn tại
ộ h ( ) ( ( )) khm t n0 sao c o T N n0.
Đơn giản hơn T(N) = o(p(N)) nếu T(N) =
O( ( )) à ( ) Ө( ( ))
Vũ Anh Dũng - Khoa CNTT 16
p N v T N ≠ p N .
Đánh giá thuật toán
Khi T(N) = O(f(N)), là T(N) tăng với tỉ
lệ không nhanh hơn f(N); do vậy f(N)
là biên trên của T(N).
Do điều này ngụ ý rằng f(N) =
Ω(T(N)), chúng ta nói rằng T(N) là biên
dưới của f(N) .
Vũ Anh Dũng - Khoa CNTT 17
Đánh giá thuật toán
Ví dụ : T(N) = 1000N, n0 = 1000, c=1,
f(N)=N2
N3 tăng nhanh hơn N2, nên ta có thể nói
rằng N2 = O(N3) hay N3 =Ω(N2)
Xét g(N) = 2N2, thì g(N) = O(N3), và g(N)
O(N2) đều đúng về mặt kỹ thuật nhưng=
lựa chọn O(N2)là đáp án tốt nhất.
Vũ Anh Dũng - Khoa CNTT 18
Các quy tắc
Quy tắc 1.
Nếu T1(N) = O(f(N)) và T2(N) = O(g(N)) thì ,
(a) T1(N) + T2(N) = O(f(N) + g(N)) ( hay
max(O(f(N)) O(g(N))) ), ,
(b) T1(N) * T2(N) = O(f(N) *g(N)).
Quy tắc 3 .
LogkN = O(N) đối với hằng số k bất kì. Điều này
ói lê ằ á hà l it tă ất hậ
Vũ Anh Dũng - Khoa CNTT 19
n n r ng c c m ogar ng r c m
Độ phức tạp
độ phức tạp hằng số, O(c). Số phép tính/thời gian chạy/dung lượng bộ nhớ
không phụ thuộc vào độ lớn đầu vào.
độ phức tạp tuyến tính, O(n). Số phép tính/thời gian chạy/dung lượng bộ
nhớ có xu hướng tỉ lệ thuận với độ lớn đầu vào. Chẳng hạn như tính tổng
các phần tử của một mảng một chiều.
độ phức tạp đa thức, O(P(n)), với P là đa thức bậc cao (từ 2 trở lên). Chẳng
h hư á th tá tí h t á ới ả hiề hiề (tí h đị h thứạn n c c ao c n o n v m ng n u c u n n c ma
trận).
độ phức tạp logarit, O(logn) (chú ý: bậc của nó thấp hơn so với O(n)) .
Chẳng hạn thuật toán Euclid để tìm ước số chung lớn nhất.
độ phức tạp hàm bậc 2, O(N2).
độ phức tạp hàm mũ, O(2n). Trường hợp này bất lợi nhất và sẽ rất phi thực
tế nếu thực hiện thuật toán với độ phức tạp này.
Vũ Anh Dũng - Khoa CNTT 20
Độ phức tạp
Không nên nói T(N) = O(2N2) hay T(N) =
0(N2 – 4 – N).
Trong cả hai trường hợp này, dạng đúng
là T(N) = O(N2) .
Nói chung có thể bỏ qua các số hạng bậc
thấp và vứt bỏ các hằng số
Vũ Anh Dũng - Khoa CNTT 21
Bài toán tổng dãy con lớn nhất
Cho các số nguyên (có thể âm) A1, A2, . . . ,
A ì iá ị lớ hấ ủN t m g tr n n t c a
∑ j kA
Ví d Với đầ à 2 11 4 13 5 2
=ik
ụ: u v o - , , - , , - , - ,
đáp án là 20 (A2 đến A4)
Vũ Anh Dũng - Khoa CNTT 22
Bài toán tổng dãy con lớn nhất
Đầu vào
Thời gian thuật toán
1 2 3 4
Cỡ O(N3) O(N2) O(NlogN) O(N)
N = 10 0.000009 0.000004 0.000006 0.000003
N = 100 0.002580 0.000109 0.000045 0.000006
N = 1000 2.281013 0.010203 0.000485 0.000031
N = 10000 NA 1.2329 0.005712 0.000317
N 100000 NA 135
0.064618 0.003206
=
Thời gian chạy ứng với các thuật toán khác nhau
Vũ Anh Dũng - Khoa CNTT 23
Cách tính thời gian chạy
Viết đoạn chương trình tính :
∑N 3
int sum( int n )
=i
i
1
{
int partialSum;
1 partialSum = 0;
2 for( int i = 1; i <= n; i++ )
3 partialSum += i * i * i;
4 return partialSum;
Vũ Anh Dũng - Khoa CNTT 24
}
Cách tính thời gian chạy
Phân tích :
Các khai báo không chiếm thời gian.
Các dòng 1 và 4 được tính mỗi dòng một đơn vị thời gian.
Dòng 3 được tính bốn đơn vị thời gian thực hiện (hai phép nhân, một
phép cộng, và một phép gán) và dòng này được thực hiện N lần, nâng
tổng thời gian chạy lên 4N đơn vị.
Dòng 2 Nn chứa thời gian khởi tạo i, kiểm tra i < N , và tăng i. Thời
gian của các thao tác này gồm 1 cho việc khởi tạo, N + 1 cho các kiểm
tra, và N cho các phép tăng, tổng cộng là 2N + 2.
Chúng ta còn chưa kể đến thời gian gọi hàm và trả về giá trị nên tổng
cộng thời gian lên đến 6N + 4.
Vũ Anh Dũng - Khoa CNTT 25
Do vậy, chúng ta kết luận hàm của thời gian chạy là O(N ).
Các quy tắc
Quy tắc 1 – các vòng lặp FOR.
Thời gian chạy của một vòng lặp for là thời gian chạy
của các lệnh bên trong vòng lặp (kể cả các phép kiểm
tra) nhân với số lần lặp.
Q tắ 2 Cá ò lặ lồ h uy c – c v ng p ng n au
Phân tích các vòng lặp này từ trong ra ngoài. Tổng thời
gian chạy của một câu lệnh trong một nhóm các vòng
lặp lồng nhau là thời gian chạy của lệnh này nhân với cỡ
của các vòng lặp.
Vũ Anh Dũng - Khoa CNTT 26
Các quy tắc
Quy tắc 3 – Các lệnh tuần tự.
Đối với những lệnh này, chỉ đơn thuần là cộng dồn
Quy tắc 4 – if/else
if(condition) S1
l S2e se
Thời gian chạy không bao giờ vượt quá thời gian chạy
phép kiểm tra điều kiện cộng với thời gian chạy lớn nhất
của S1 và S2.
Vũ Anh Dũng - Khoa CNTT 27
Một số trường hợp đệ quy
Ví dụ, hàm sau đây thực ra chỉ là một vòng lặp đơn
giản và là O(N ):
long factorial(int n)
{
if (n <= 1 )
return 1;
else
return n * factorial(n 1); -
}
Vũ Anh Dũng - Khoa CNTT 28
Một số trường hợp đệ quy
Ví dụ, hàm sau đây có độ phức tạp hàm mũ:
long fib (int n)
{
1 if(n <= 1)
2 return 1;
else
3 return fib (n - 1) + fib (n - 2);
}
Gợi ý :
T(n) = T(n-2) + T(n-1) + 2
fib( ) (3/2)n
Vũ Anh Dũng - Khoa CNTT 29
n >
Một số trường hợp đệ quy
Ví dụ, hàm sau đây có độ phức tạp hàm mũ:
fib(n) < (5/2)n
Bằng cách tạo một mảng đơn giản và sử dụng vòng
lặp, thời gian chạy có thể được rút ngắn một cách cơ
bản.
“Đừng tính bất cứ cái gì quá một lần”
Vũ Anh Dũng - Khoa CNTT 30
Các thuật toán cho bài tổng dãy
con lớn nhất
Ví dụ trong file MaxSumTest.cpp
Thuật toán 1 :
4 int maxSubSum1(const vector & a)
5 {
6 int maxSum = 0;
7
8 for (int i = 0; i < a.size(); i++)
9 for (int j = i; j < a size(); j++) .
10 {
11 int thisSum = 0;
12
13 for (int k = i; k < j); k++)
14 thisSum += a[k];
15
16 if(thisSum > maxSum)
17 maxSum = thisSum;
18 }
19
20 return maxSum;
Vũ Anh Dũng - Khoa CNTT 31
21 }
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 1
Đánh giá thuật toán 1
Số bước tính toán :
∑ ∑ ∑−
=
−
= =
1
0
1
1
N
i
N
ij
j
ik
Trước tiên ta có :
∑j 11 +−=
=
ij
ik
Vũ Anh Dũng - Khoa CNTT 32
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 1
Tiếp theo :
∑−
=
−+−=+−
1
2
))(1()1(
N
ij
iNiNij
∑∑
=
−
=
+−+−=−+−
N
i
N
i
iNiNiNiN
1
1
0 2
)2)(1(
2
))(1(
131 NNN
2
23
2
)1()
2
3(
6
)12)(1(
2
1
1)23(
2
)
2
(
2
2
1
2
11
2
NNNNNNNNN
NNiNi
iii
+++++−++=
++++−= ∑∑∑
===
Độ phức tạp tính toán cho thuật toán 1 : O(N 3)
6
23 23 NNN ++=
Vũ Anh Dũng - Khoa CNTT 33
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 2
Chúng ta đưa ra cải tiến thuật toán 1 bằng cách loại
bỏ 1 vòng lặp for và độ phức tạp chỉ còn O(N 2)
Thuật toán 2 :
4 int maxSubSum2(const vector & a)
5 {
6 int maxSum = 0;
7
8 for( int i = 0; i < a.size( ); i++ )
9 {
10 int thisSum = 0;
11 for( int j = i; j < a.size( ); j++ )
12 {
13 thisSum += a[ j ];
14
15 if( thisSum > maxSum )
16 maxSum = thisSum;
17 }
18 }
Vũ Anh Dũng - Khoa CNTT 34
19
20 return maxSum;
21 }
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 3
Thuật toán 3 :
Tổng lớn nhất các dãy con có thể ở một trong ba vị trí :
Có thể trong nửa trái hay nửa phải của đầu vào, hoặc nằm ở
giữa, thuộc về cả hai nửa.
ầ ể ằ Hai trường hợp đ u có th giải được b ng đệ quy.
Trường hợp cuối, tìm tổng lớn nhất trong nửa đầu bao gồm
cả phần tử cuối cùng của nửa đầu và tìm tổng lớn nhất ,
trong nửa cuối bao gồm cả phần tử đầu tiên trong nửa cuối.
Hai tổng này được cộng với nhau.
Vũ Anh Dũng - Khoa CNTT 35
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 3
Thuật toán 3 :
6 int maxSumRec( const vector & a, int left, int right )
7 {
8 if( left == right ) // Base case
9 if( a[left] > 0 )
10 return a[left];
11 else
12 return 0;
13
14 int center = ( left + right ) / 2;
15 int maxLeftSum = maxSumRec( a, left, center );
16 int maxRightSum = maxSumRec( a, center + 1, right );
17
18 int maxLeftBorderSum = 0, leftBorderSum = 0;
19 for( int i = center; i >= left; i-- )
20 {
21 leftBorderSum += a[ i ];
Vũ Anh Dũng - Khoa CNTT
36
22 if( leftBorderSum > maxLeftBorderSum )
23 maxLeftBorderSum = leftBorderSum;
24 }
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 3
Thuật toán 3 :
25
26 int maxRightBorderSum = 0, rightBorderSum = 0;
27 for( int j = center + 1; j <= right; j++ )
28 {
29 rightBorderSum += a[ j ];
30 if( rightBorderSum > maxRightBorderSum )
31 maxRightBorderSum = rightBorderSum;
32 }
33
34 return max3( maxLeftSum, maxRightSum,
35 maxLeftBorderSum + maxRightBorderSum );
36 }
42 int maxSubSum3( const vector & a )
43 {
44 return maxSumRec( a, 0, a.size( ) - 1 );
Vũ Anh Dũng - Khoa CNTT 37
45 }
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 3
Đánh giá thuật toán 3 :
T(1) = 1
T(N) = 2*T(N/2) + N
T(1) = 1, T(2) = 2*1+2 = 2*2, T(4) = 2*4+4,
T(8)= 2*12+8 = 8*4, T(16) = 32*2+16=16*5
Vậy nếu N=2k thì T(N) = N*(k+1)=NlogN+N
T(N) = O(NlogN)
Vũ Anh Dũng - Khoa CNTT 38
Các thuật toán cho bài tổng dãy
con lớn nhất – Thuật toán 4
Có độ phức tạp tuyến tính O(N )
Thuật toán 4 :
4 int maxSubSum4( const vector & a )
5 {
6 int maxSum = 0, thisSum = 0;
7
8 f ( i t j 0 j < i () j++ )or n = ; a.s ze ;
9 {
10 thisSum += a[ j ];
11
12 if( thisSum > maxSum )
13 maxSum = thisSum
14 else if( thisSum < 0 )
15 thisSum = 0;
16 }
17
Vũ Anh Dũng - Khoa CNTT 39
18 return maxSum;
19 }
Thuật toán Euclid
Tìm ước số chung lớn nhất
Định lý :
Định lý 2.1.
Nếu M > N, thì M mod N < M/2.
Độ phức tạp tính toán :
O(logN )
Vũ Anh Dũng - Khoa CNTT 40