Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan cấu trúc dữ liệu và giải thuật - Đỗ Ngọc Như Loan

Tổng quan về 
Cấu trúc dữ liệu & Giải thuật 
GV: Đỗ Ngọc Như Loan 
Cấu trúc dữ liệu là gì? 
C ấ u trúc d ữ li ệu là cách t ổ ch ứ c lưu trữ d ữ li ệ u sao cho hi ệ u qu ả nh ấ t 
Thế nào là hiệu quả? 
1. Chính xác 
2. Dùng ít b ộ nh ớ 
3. Khả năng tìm kiếm/truy xuất 
4. Khả năng cập nhật , thêm (modification, insertion / deletion) 
5. Đơn giản , dễ hiểu 
Giải thuật là gì? 
Thu ậ t toán là m ộ t phương pháp bao g ồ m m ộ t dãy các bư ớ c tính toán để giải quyết một bài toán. Thuật toán có thể được diễn tả dưới ngôn ngữ tự nhiên ( tiếng Việt , tiếng Anh ), mã giả hay ngôn ngữ lập trình (C ++, Java ) 
Thế nào là một thuật toán tốt ? 
1. Đúng đắn 
2. Nhanh 
3. Ít bộ nhớ 
4. Đ ơn giản , dễ hiểu 
Ví dụ 
Tìm x trong dãy a1, a2, ...., an 
Input: Số x, dãy n số a1, a2, ..., an 
Output: Một giá trị logic true hoặc false 
Search(x , a, n) 
for i  1 to n 
	do if ai = x 
	 	 then return true 
 return false 
Một vấn đề có thể được giải quyết bẳng nhiều thuật toán khác nhau 
Ví dụ 
Tính tổng các số nguyên từ 1 đến n. 
Input: n (n >1) 
Output: Tổng các số nguyên từ 1 đến n 
Cách 1 
sum = 0; 
for (int i = 1; i <= n; i++) 
	 sum = sum + i; 
Cách 2 
sum = n*(n+1)/2; 
Cách 1 
sum = 0; 
for (int i = 1; i <= n; i++) 
	 sum = sum + i; 
Cách 2 
sum = n*(n+1)/2; 
Độ phức tạp O(n) 
Độ phức tạp O(1) 
ĐỘ PHỨC TẠP THUẬT TOÁN 
Độ phức tạp của giải thuật là chi phí về tài nguyên của hệ thống (chủ yếu là thời gian, bộ nhớ, CPU, đường truyền) cần thiết để thực hiện giải thuật 
Độ phức tạp về không gian (dung lượng bộ nhớ sử dụng) 
Độ phức tạp về thời gian 
Phân tích giải thuật (Analyzing of Algorithm) là quá trình tìm ra những đánh giá về tài nguyên cần thiết để thực hiện giải thuật 
ĐỘ PHỨC TẠP THUẬT TOÁN 
Độ phức tạp về thời gian của giải thuật: 
• Được qui về đếm số lệnh cần thực thi của giải thuật 
• Đó là một hàm T (n) phụ thuộc vào kích thước n của input 
• Coi như có một máy trừu tượng (abstract machine) để thực hiện giải thuật 
ĐỘ PHỨC TẠP THUẬT TOÁN 
• Thời gian tối thiểu để thực hiện giải thuật với kích thước đầu vào n gọi là thời gian chạy tốt nhất (best-case) của giải thuật 
• Thời gian nhiều nhất để thực hiện giải thuật với kích thước đầu vào n được gọi là thời gian chạy xấu nhất (worst-case) của giải thuật 
• Thời gian trung bình để thực hiện giải thuật với kích thước đầu vào n được gọi là thời gian chạy trung bình (average case) của giải 
thuật 
Ví dụ 
Đánh giá độ phức tạp về thời gian của giải thuật 
Search(x, a, n) 
for i  1 to n 
	do if ai = x 
	then return true 
return false 
  dssdsdsssssssssssslkcddkcf;dxkac 
BIỂU DIỄN THỜI GIAN CHẠY BỞI KÝ HIỆU O 
Giả sử f(n) và g (n) là hàm thực không âm của đối số nguyên dương n , 
ta nói f(n ) = O(g(n)) 
nếu có hằng số c > 0 và số nguyên dương N sao cho f(n ) = N 
Nếu giải thuật có thời gian chạy tốt nhất (trung bình, xấu nhất) là T(n) và T(n) = O(g(n)) thì ta nói độ phức tạp của giải thuật trong trường hợp tốt nhất (trung bình, xấu nhất) là O(g(n)) 
Ví dụ: 
Giả sử f(n) = 5n 3 + 2n 2 + 13n + 6 , ta có: 
f(n) = 5n 3 + 2n 2 + 13n + 6 =1) 
f(n) = O(n 3 ) 
Tổng quát nếu f(n) là một đa thức bậc k của n: 
f(n) = a k n k + a k-1 n k-1 + ... + a 1 n + a 0 thì f(n) = O(n k ) 
Quy Tắc 
QUY TẮC CỘNG: Nếu đoạn chương trình P1 có thời gian thực hiện T1(n) = O(f(n)) và đoạn chương trình P2 có thời gian thực hiện là T2(n) = O(g(n )) thì thời gian thực hiện P1 rồi đến P2 tiếp theo sẽ là : T1(n ) + T2(n) = O(f(n) + g(n)) 
QUY TẮC NHÂN: Nếu đoạn chương trình P có thời gian thực hiện là T(n) = O(f(n )). Khi đó, nếu thực hiện k(n) lần đoạn chương trình P với k(n) = O(g(n )) thì độ phức tạp tính toán sẽ là O(g(n ). f(n )) 
QUY TẮC MAX: Nếu đoạn chương trình P có thời gian thực hiện T(n) = O(f(n) + g(n)) thì có thể coi đoạn chương trình đó có độ phức tạp tính toán O(max(f(n),g(n))). 
Độ phức tạp (tăng dần) 
• O(1) Hằng số 
• O(log 2 n ) Logarithm 
• O(n) Tuyến tính 
• O(nlog 2 n ) n log n 
• O(n 2 ) Bậc hai 
• O(n 3 ) Bậc ba 
• O(n m ) Đa thức 
• O(m n ), m >= 2 Hàm mũ 
• O(n!) Giai thừa 
VÍ DỤ 
Viết và phân tích giải thuật tính giai thừa của số tự nhiên n. 
VÍ DỤ 
Factorial(n) 
if n = 0 or n = 1 
	then return 1 
else if n > 1 
	 then return n*Factorial(n-1) 
VÍ DỤ 
Gọi T(n) là thời gian chạy của thuật giải 
	O(1), n=0, 1 
	T(n)= 
	T(n-1)+O(1), n>1 
T(n) 	= T(n-1) + c 
	 	= T(n-2)+c +c =T(n-2) + 2c 
	= T(n-3)+c + 2c = T(n-3) + 3c 
	. 
	= T(n-(n-1)) + (n-1)c = T(1) + (n-1)c = c + 	(n-1)c = nc 
T(n) = O(n) (tương đương với giải thuật không đệ qui) 
Luyện tập 1 
for (i = 0 ; i < n ; i++) 
	 if (A[i] % 2 == 0) 
	 	return true; 
r eturn false; 
Độ phức tạp? 
Luyện tập 2 
s um = 0; 
for (i = 0 ; i < 2 0 ; i++) 
	sum = sum + i;	 
Độ phức tạp? 
Luyện tập 3 
for (i = 0 ; i < n ; i++) 
	for (j = 0 ; j < n ; j ++) 
	A[i ][j] = 0; 
for (i = 0 ; i < n ; i++) 
	 A[i ][i] = 1 ; 
Độ phức tạp? 
Luyện tập 4 
sum = 0; 
for ( i = 0; i < n; i + +) 
	for ( j = i + 1; j < = n; j + +) 
	for ( k = 1; k < 10; k + +) 
	 	sum = sum + i * j * k ; 
Độ phức tạp? 
Luyện tập 5 
sum = 0; 
for ( i = 0; i < n; i + +) 
	for ( j = i + 1; j < = n; j + +) 
	for ( k = 1; k < m; k + +) { 
	sum = sum + i * j * k ; 
	 	} 
Độ phức tạp? 
Luyện tập 6 
for (i = 0; I < n; I ++) 
	for (j = 0; j < m; j ++) { 
	 	int x = 0; 
	for (k = 0; k < n; k ++) 
	 	x = x + k; 
	 	for (k = 0; k < m; k++) 
	 	x = x +k; 
	 } 
Độ phức tạp? 
MỘT SỐ LƯU Ý 
Nếu bài toán có thuật giải với thời gian chạy xấu nhất là đa thức , O(n m ), thì bài toán gọi là được giải tốt 
Nếu bài toán không có thuật giải với thời gian chạy xấu nhất là đa thức thì bài toán gọi là khó giải (intractable problem) 
Nếu bài toán khó đến mức không thể xây dựng được thuật giải thì nó được gọi là không giải được (unsolvable problem) 
Phân tích độ phức tạp chủ yếu dựa trên kỹ thuật đếm và biểu diễn hệ thức truy hồi 
Có hai phương pháp chính để giải hệ thức truy hồi: Thay thế lặp và áp dụng trực tiếp các công thức toán học 
Phân tích trường hợp trung bình thường phức tạp hơn và cần thêm các công cụ toán học như lý thuyết xác suất, hàm sinh 
Trong nhiều trường hợp chỉ cần tính thời gian chạy xấu nhất