Bài giảng Cấu trúc dữ liệu 1: Chương 1

Ạ Ọ Ạ Ọ

ƯỜ ƯỜ

NG Đ I H C AN GIANG NG Đ I H C AN GIANG Ậ Ậ

Ệ Ệ

TR TR Ỹ Ỹ

ƯỜ ƯỜ

KHOA K THU T CÔNG NGH MÔI TR KHOA K THU T CÔNG NGH MÔI TR

NG NG

Ữ Ệ Ữ Ệ

Ấ Ấ

C U TRÚC D LI U 1 C U TRÚC D LI U 1

Giảng viên phụ trách:

HUỲNH CAO THẾ CƯỜNG

Bộ môn Tin học

email: hctcuong@agu.edu.vn

11 Chương 1. TỔNG QUAN CẤU TRÚC DỮ LIỆU Chương 1. TỔNG QUAN CẤU TRÚC DỮ LIỆU

Cấu trúc dữ liệu (Data Structures) Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) Giải thuật (Algorithms) Tính toán độ phức tạp của giải thuật (Computational

complexity of algrorithms)

Phân tích giải thuật (Algorithm Analysis)

2 Cấu trúc dữ liệu (Data Structures) Cấu trúc dữ liệu (Data Structures)

là một tập hợp.

Cấu trúc dữ liệu dùng để tổ chức dữ liệu  Thường có nhiều hơn một thành phần  Có các thao tác hợp lý trên dữ liệu  Dữ liệu có thể được kết nối với nhau (ví dụ: array) như

3 Kiểu dữ liệu trừu tượng (ADT) Kiểu dữ liệu trừu tượng (ADT)

Một kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) là tập hợp các đối tượng và được xác định hoàn toàn bởi các phép toán có thể biểu diễn trên các đối tượng đó.

ADT là một mô hình toán của cấu trúc dữ liệu xác định kiểu dữ liệu được lưu trữ, các thao tác được hỗ trợ trên dữ liệu đó và kiểu của các tham số trong từng thao tác.

4 Kiểu dữ liệu trừu tượng (ADT) Kiểu dữ liệu trừu tượng (ADT)

 Đơn/nguyên tử: int, char, …  Có cấu trúc: array, struct,…

Có hai loại ADT

Ngoài những ADT do ngôn ngữ lập trình cung cấp, người lập trình có tạo ra các ADT của riêng mình

Trong C, các ADT do người dùng định nghĩa sẽ thông qua kiểu cấu trúc (struct), các thao tác được xây dựng bằng các hàm (functions)

5 Kiểu dữ liệu trừu tượng (ADT) Kiểu dữ liệu trừu tượng (ADT)

 Tạo lập đối tượng mới  Biến đổi các đối tượng của ADT

– Mang lại những thay đổi cần thiết cho đối tượng

 Quan sát

– Cho biết trạng thái của đối tượng

 Chuyển đổi kiểu

– Chuyển kiểu từ kiểu này sang kiểu khác

 Vào ra dữ liệu

– Nhập/xuất giá trị cho đối tượng

Các lớp thao tác của một ADT

6 Kiểu dữ liệu trừu tượng (ADT) Kiểu dữ liệu trừu tượng (ADT)

 Cấu thành bởi: – Họ tên – Ngày sinh – Nơi sinh – Phái  Phép toán:

– Tạo mới một person (với thông tin đầy đủ) – Hiển thị thông tin về một person – ….

Person

7 Tại sao cần phải học Cấu trúc dữ liệu và Giải Tại sao cần phải học Cấu trúc dữ liệu và Giải thuật? thuật?

 Tại sao lại cần phải học giải thuật? Vai trò của giải

thuật? Những vấn đề nào sẽ cần giải quyết bằng giải thuật? Giải thuật:

 Là một khái niệm quan trọng nhất trong tin học. Thuật ngữ này xuất phát từ nhà tóa học Ảrập Abu Ja’far Mohammed ibn Musa al Khowarizmi (khoảng năm 825)

 Thuật toán nổi tiếng nhất, có từ thời kỳ cổ Hy Lạp là

thuật toán Euclid.

Giải thuật?

 Là một phương pháp giải quyết vấn đề thích hợp để 8

cài đặt như một chương trình máy tính.

Tại sao cần phải học Cấu trúc dữ liệu và Giải Tại sao cần phải học Cấu trúc dữ liệu và Giải thuật? thuật?

 A finite sequence of steps for solving a logical or mathematical problem or performing a task. (The Microsoft Computer Dictionary, Fifth Edition )

 A computable set of steps to achieve a desired result.  Informally, an algorithm is any well-defined

computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output (Introduction to Algorithms, 2nd, Thomas H. Cormen, 2001)

Algorithm:

9 Tại sao cần phải học Cấu trúc dữ liệu và Giải Tại sao cần phải học Cấu trúc dữ liệu và Giải thuật? thuật?

 Được tạo ra để phục vụ cho các giải thuật  Phải hiểu cấu trúc dữ liệu để hiểu giải thuật (cid:0)

để giải

quyết vấn đề

 Các giải thuật đơn giản có thể cần đến cấu trúc dữ liệu

phức tạp

 Các giải thuật phức tạp có thể chỉ dùng các cấu trúc

dữ liệu đơn giản

Cấu trúc dữ liệu?

ữ ệ ấ ả ươ C u trúc d li u + Gi ậ i thu t = Ch ng trình

10 Kiểu dữ liệu Kiểu dữ liệu

 Tên kiểu dữ liệu  Miền giá trị  Kích thước lưu trữ  Tập các toán tử, phép toán tác động trên kiểu dữ liệu

ĐN kiểu dữ liệu Các thuộc tính của 1 kiểu dữ liệu

 Kiểu chuỗi ký tự (string), Kiểu mảng (array)  Kiểu mẩu tin (struct)  Kiểu tập hợp (union)

Một số kiểu dữ liệu có cấu trúc cơ bản

11 Tại sao cần phải học Cấu trúc dữ liệu và Giải Tại sao cần phải học Cấu trúc dữ liệu và Giải thuật? thuật?

 Giải quyết các vấn đề về tính toán?  Việc giải quyết vấn đề nhanh hơn?  Khả năng truy xuất nhiều dữ liệu hơn?

Dùng máy tính để:

 Kỹ thuật có thể tăng khả năng giải quyết vấn đề

bằng nhân tố hằng.

 Thiết kế giải thuật tốt có thể giúp giải quyết vấn đề

tốt hơn nhiều và có thể rẻ hơn.

 Một siêu máy tính không thể giúp một giải thuật tồi

làm việc tốt hơn

Kỹ thuật vs. Thực thi/Giá

12 Một số tính chất chung Một số tính chất c

của các thuật toán hung của các thuật toán

 Đầu vào (input): có các giá trị đầu vào xác định.  Đầu ra (ouput): từ tập các giá trị đầu vào, thuât toán sẽ tạo các

giá trị đầu ra, xem là nghiệm của bài toán.

 Tính xác định (definiteness): các bước của thuật toán phải được

xác định một cách chính xác.

 Tính hữu hạn (finiteness): một thuật toán chứa một số hữu hạn

các bước (có thể rất lớn) với mọi tập đầu vào.

 Tính hiệu quả(effectiveness): mỗi bước phải thực hiện chính xác,

trong khoảng thời gian hữu hạn.

 Tính tổng quát(general): thuật toán phải áp dụng được cho một

họ các vấn đề.

13 Ví dụVí dụ

Ví dụ: Mô tả thuật toán tìm phần tử lớn nhất trong một

đầu tiên.

 Bước 2: Nếu số nguyên kế tiếp lớn hơn giá trị cực đại

tạm thời thì gán giá trị cực đại tạm thời bằng số nguyên đó.

 Bước 3: Lặp lại bước 2 nếu còn số nguyên trong dãy.  Bước 4: Dừng khi không còn số nguyên trên dãy. Số nguyên lớn nhất trong dãy là giá trị cực đại tạm thời.

dãy hữu hạn các số nguyên  Bước 1: Đặt giá trị cực đại tạm thời bằng số nguyên

14 Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân

// Tìm tuyến tính

linearSearch(int a[], int x, int n)

int {

i = 0;

int while (i < n) && (a[i] != x)

i++;

return (i == n);

}

15 Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân

// Tìm nhị phân

int binarySearch(int a[], int x, int n)

{

left = 0, right = N - 1, middle;

int do {

middle = (left + right) / 2; if (a[middle] == x)

return TRUE; else if (x < a[middle])

right = middle – 1;

else left = middle + 1;

} while (left <= right); return FALSE;

}

16 Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân

 Với tìm kiếm tuần tự, giả sử x không có trong mảng a,

giải thuật phải xử lý đầy đủ n lần.

 Với tìm kiếm nhị phân, dù x có hay không có trong a thì

số lần tìm kiếm tối đa chỉ là log2n = 5.

Để so sánh hai giải thuật, sử dụng n = 32

17 Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân

Tuần tự

Nhị phân

n

256

1024

1048576

4.294.967.296 4.294.967.296

18 Ví dụ so sánh - Fibonacci Ví dụ so sánh - Fibonacci

// Tính Fibonacci(n) int fib1(int n) if (n <= 1) {

return n;

else

return fib1(n - 1) + fib1(n - 2);

}

i (cid:0) n) được tính trong

Gọi T(n) là số lượng các Fi (0 (cid:0) giải thuật đệ qui: T(n) > 2n/2

19 Ví dụ so sánh - Fibonacci Ví dụ so sánh - Fibonacci

// Tính Fibonacci(n) int fib2(int n) {

f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++)

f[i] = f[i - 1] + f[i - 2];

return f[n];

}

20 Ví dụ so sánh - Fibonacci Ví dụ so sánh - Fibonacci

n + 1

2n/2

fib2()

fib1()

1,048,576

41 ns

1048 μs

1.1 × 109

61 ns

1 s

1.1 × 1012

81 ns

18 min

100

101

1.1 × 1015

101 ns

13 days

120

121

1.2 × 1018

121 ns

36 years

160

161

1.2 × 1024

161 ns

3.8 × 107 years

200

201

1.3 × 1030

201 ns

4 × 1013 years

21 Phân tích thuật toán Phân tích thuật toán

Độ phức tạp về không gian (space complexity) Độ phức tạp về thời gian (time complexity) Độ phức tạp về giải thuật (complexity of algorithm)

22 space complexity) Độ phức tạp về không gian ((space complexity) Độ phức tạp về không gian

 Bộ nhớ  Sử dụng CPU  Băng thông  …

Chiếm tài nguyên của máy:

23 time complexity) Độ phức tạp về thời gian ((time complexity) Độ phức tạp về thời gian

Tính hiệu quả của giải thuật được kiểm tra bằng

phương pháp thực nghiệm, thông qua các bộ dữ liệu thử:  Phụ thuộc vào ngôn ngữ lập trình.  Trình độ, kỹ năng có được của người viết.  Phần cứng (máy tính) dùng để thử nghiệm.  Sự phức tạp của việc xây dựng một bộ dữ liệu thử.

24 Tiêu chuẩn đánh giá một giải thuật là tốt Tiêu chuẩn đánh giá một giải thuật là tốt

Một giải thuật được xem là tốt nếu nó đạt các tiêu

chuẩn sau:  Thực hiện đúng.  Tốn ít bộ nhớ.  Thực hiện nhanh.

Trong khuôn khổ môn học này, chúng ta chỉ quan tâm

đến tiêu chuẩn thực hiện nhanh.

25 complexity of Độ phức tạp về giải thuật ((complexity of Độ phức tạp về giải thuật algorithm) algorithm)

Mang tính hình thức. Phép đo độc lập với máy tính, ngôn ngữ máy tính,

người lập trình, … hay những “tiểu tiết”: tăng/giảm chỉ số vòng lặp, sự khởi tạo, gán, …

Thời gian thực thi của một giải thuật sẽ tăng theo kích thước dữ liệu và thời gian này tỉ lệ với số lượng các thao tác cơ sở.

Độ phức tạp của giải thuật là một hàm số trên kích

thước dữ liệu.

26 complexity of Độ phức tạp về giải thuật ((complexity of Độ phức tạp về giải thuật algorithm) algorithm)

Những thao tác cơ sở có thể là:

- Phép so sánh - Phép chuyển dời - Phép toán số học, …

Thao tác cơ sở là thao tác mang lại hiệu quả cao nhất.

Trong các giải thuật sắp xếp, hai thao tác cơ bản là: so

sánh và chuyển dời.

27 Độ phức tạp giải thuật (Algorithm Complexity) Độ phức tạp giải thuật (Algorithm Complexity)

 Đơn vị đo thời gian thực hiện:

– T(n) trong đó n là kích thước (độ lớn) của dữ liệu

vào. T(n) ≥ 0 với mọi n ≥ 0.

 Thông thường người ta tính thời gian thực hiện xấu

nhất (the worst case):

– T(n) là thời gian lớn nhất để thực hiện chương trình

đối với mọi dữ liệu vào có cùng kích thước n.

Thời gian thực hiện chương trình (Running Time).

28 Tỷ suất tăng (growth rate) Tỷ suất tăng (growth rate)

T(n) có tỷ suất tăng f(n) nếu tồn tại các hằng số C và

N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0.

 Giả sử T(0) = 1, T(1) = 4, tổng quát T(n) = (n+1)2  Ðặt N0 = 1 và C = 4 thì n ≥1, ∀  Ta có T(n) = (n+1)2 ≤ 4n2 với mọi n ≥ 1, tức là tỷ suất

tăng của T(n) là n2.

Ví dụ:

 T(n) = 3n3 + 2n2 là n3. Cho N0 = 0 và C = 5 ta có với

mọi n ≥ 0 thì 3n3 + 2n2 ≤ 5n3

Ví dụ:

29 Khái niệm độ phức tạp của giải thuật

 P1: T1(n) = 100n2 (tỷ suất tăng là n2)  P2 : T2(n) = 5n3 (tỷ suất tăng n3). Giải thuật nào sẽ thực hiện nhanh hơn?

 Với n < 20 thì P2 sẽ nhanh hơn P1 (T2 20 thì P1 sẽ nhanh hơn P2 (T1

Giả sử ta có hai giải thuật P1 và P2

30 Khái niệm độ phức tạp của giải thuật

 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, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”)

Khái niệm:

Ví dụ: T(n)= (n+1)2 có tỷ suất tăng là n2 nên T(n)=

(n+1)2 là O(n2)

Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt

O(C)=O(1)

hàm thể hiện độ phức tạp có các dạng thường gặp

sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn.

31 Tính toán độ phức tạp (Computational Complexity)

 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; và T1(n)=O(f(n)), T2(n)=O(g(n)) thì thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(n)=O(max(f(n),g(n)))

 Ví dụ: Lệnh gán x:=15 tốn một hằng thời gian hay

O(1), và lệnh đọc dữ liệu scanf(“%d”,&x) tốn một hằng thời gian hay O(1).Vậy thời gian thực hiện cả hai lệnh trên nối tiếp nhau là O(max(1,1))=O(1)

Qui tắc cộng

32 Tính toán độ phức tạp (Computational Complexity)

 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 và T1(n) = O(f(n)), T2(n) = O(g(n)) thì thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(n) = O(f(n).g(n))

Qui tắc nhân:

33 Tính toán độ phức tạp (Computational Complexity)

 Qui tắc tổng quát để phân tích một chương trình:

 lệnh gán, scanf, printf là O(1)  chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng => Như vậy thời gian này = thời gian thi hành một lệnh nào đó lâu nhất.

 Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN 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 là 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ì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp.

34 Tính toán độ phức tạp (Computational Complexity)

void BubbleSort(int list[], int n) { int i,j,temp;

for(i=0;i<(n-1);i++) for(j=0;j<(n-(i+1));j++)

(1) (2) (3) (4) (5) (6)

O((n-i).1) = O(n-i) O(1) O(1) O(1) O(1)

if(list[j] > list[j+1]) { temp = list[j]; list[j]= list[j+1]; list[j+1]= temp; }

}

35 Khái niệm độ phức tạp của giải thuật Khái niệm độ phức tạp của giải thuật

Giả sử ta có hai giải thuật P1 và P2 với thời gian thực hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) và T2(n) = 5n3 (với tỷ suất tăng là n3).

Khi n>20 thì T1 < T2. Sở dĩ như vậy là do tỷ suất tăng

của T1 nhỏ hơn tỷ suất tăng của T2.

Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản thân thời gian thực hiệ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, N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”).

36 Khái niệm độ phức tạp của giải thuật Khái niệm độ phức tạp của giải thuật

Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt

O(C)=O(1)

Các hàm thể hiện độ phức tạp có các dạng thường gặp

sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn.

Ba hàm cuối cùng ta gọi là dạng hàm mũ, các hàm

khác gọi là hàm đa thức.

Một giải thuật mà thời gian thực hiện có độ phức tạp là một hàm đa thức thì chấp nhận được, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến giải thuật.

Trong cách viết, ta thường dùng logn thay thế cho log2n

cho gọn.

37

Thủ tục sắp xếp “nổi bọt” Ví dụ 1: Thủ tục sắp xếp “nổi bọt” Ví dụ 1:

for(i= 0; i<=n-2; i++) for(j=n-1; j>=i+1;j--) if (a[j].key < a[j-1].key) { temp = a[j-1];

a[j] = temp;

void BubbleSort(int a[n]) { int i,j,temp; /*1*/ /*2*/ /*3*/ /*4*/ /*5*/ a[j-1] = a[j]; /*6*/ } }

38

Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt” Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt”

 Đây là chương trình sử dụng các vòng lặp xác định. Toàn bộ chương trình chỉ gồm một lệnh lặp {1}, lồng trong lệnh {1} là lệnh lặp {2}, lồng trong lệnh {2} là lệnh {3} và lồng trong lệnh {3} là 3 lệnh nối tiếp nhau {4}, {5} và {6}.

 Trước hết, cả ba lệnh gán {4}, {5} và {6} đều tốn O(1) thời

gian, việc 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) do đó vòng lặp

{2} tốn O((n-i).1) = O(n-i).

 Vòng lặp {1} có i chạy từ 1 đến n-1 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à

(cid:0) (cid:0)

T(n)

2 )O(n

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

n(n 2

(cid:0)

39 Tính độ phức tạp của hàm tìm kiếm tuần tự Tính độ phức tạp của hàm tìm kiếm tuần tự

linearSearch(int a[], int x, int n)

return 1;

int { /* 1*/ int index = 0; /* 2*/ while (index < n) { /* 3*/ /* 4*/ if (a[index] = = x) index ++;

}

return 0;

/* 5*/ }

40 Tính độ phức tạp của hàm tìm kiếm tuần tự Tính độ phức tạp của hàm tìm kiếm tuần tự

 Ta thấy các lệnh {1}, {2}, và {5} nối tiếp nhau, do đó độ phức tạp của hàm linearSearch chính là độ phức tạp lớn nhất trong 3 lệnh này. Dễ dàng thấy rằng ba lệnh {1}, {5} đều có độ phức tạp O(1) do đó độ phức tạp của hàm linearSearch chính là độ phức tạp của lệnh {2}. Lồng trong lệnh {2} là lệnh {3} và {4}. Lệnh {3}, {4} có độ phức tạp O(1).

 Lệnh {2} là một vòng lặp không xác định, nên ta không biết nó sẽ lặp bao nhiêu lần, nhưng trong trường hợp xấu nhất (tất cả các phần tử của mảng a đều khác x, ta phải xét hết tất cả các a[i], i có các giá trị từ 0 đến n-1) thì vòng lặp {2} thực hiện n lần, do đó lệnh {2} tốn O(n). Vậy ta có T(n) = O(n).

41 complexity of Độ phức tạp về giải thuật ((complexity of Độ phức tạp về giải thuật algorithm) algorithm)

void ExchangeSort(int n, int a[])

{

for (i = 0; i < n - 1; i++)

for (j = i + 1; j< n; j++)

if (a[j] < a[i]) swap(a[i], S[j]);

}

(cid:0)



nT )(

(

nn ( 2

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

42 complexity of Độ phức tạp về giải thuật ((complexity of Độ phức tạp về giải thuật algorithm) algorithm)

void MatrixMult(int n, A[][], B[][], C[][]) {

for (i = 0; i < n; i++)

for (j = 0; j < n; j++) {

C[i][j] = 0; for (k = 0; k < n; k++) C[i][j] = C[i][j] + A[i][k] * B[k][j];

}

(cid:0) (cid:0) (cid:0) (cid:0)

nnn

n

nT )(

43 Ðộ phức tạp của chương trình Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui có gọi chương trình con không đệ qui

Giả sử ta có một hệ thống các chương trình gọi nhau

theo sơ đồ sau

B

B1

B11

A

C

B2

B12

44 Phân tích các chương trình đệ qui Phân tích các chương trình đệ qui

Có thể thấy hình ảnh chương trình đệ quy A như

A

Để phân tích các các chương trình đệ quy ta cần:

 Thành lập phương trình đệ quy.  Giải phương trình đệ quy, nghiệm của phương trình đệ quy sẽ là thời gian thực hiện của chương trình đệ quy.

45

Chương trình đệ quy Chương trình đệ quy

Để giải bài toán kích thước n, phải có ít nhất một

trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k

Ví dụ : Chương trình đệ quy tính n!

int Giai_thua(int n) { if (n==0) return 1; else return (n* Giai_thua(n-1));

};

Trong ví dụ trên, n=0 là trường hợp dừng và

k=n-1.

46

Thành lập phương trình đệ quy Thành lập phương trình đệ quy

 Phương trình đệ quy là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k), trong đó T(n) và T(k) là thời gian thực hiện chương trình có kích thước dữ liệu nhập tương ứng là n và k, với k < n.

 Ðể thành lập được phương trình đệ quy, ta phải căn cứ vào

chương trình đệ quy.

 Ứng với trường hợp đệ quy dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n).

 Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi

đệ quy với kích thước k ta sẽ có bấy nhiêu T(k).

 Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n).

47

Thành lập phương trình đệ quy Thành lập phương trình đệ quy

Dạng tổng quát của một phương trình đệ quy sẽ là:

(cid:0)

(cid:0) (cid:0)

T(n)

(cid:0) (cid:0)

C(n) F(T(k))

d(n)

C(n) là thời gian thực hiện chương trình ứng với

trường hợp đệ quy dừng.

F(T(k)) là một đa thức của các T(k). d(n) là thời gian để phân chia bài toán và tổng hợp

các kết quả.

48

Ví dụ về phương trình đệ quy của chương trình đệ quy tính Ví dụ về phương trình đệ quy của chương trình đệ quy tính n!n!

 Gọi T(n) là thời gian tính n!.  Thì T(n-1) là thời gian tính (n-1)!.  Trong trường hợp n = 0 thì chương trình chỉ thực hiện một

lệnh return 1, nên tốn O(1), do đó ta có T(0) = C1.  Trong trường hợp n>0 chương trình phải gọi đệ quy

Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và return tích số.

 Thời gian để thực hiện phép nhân và return là một hằng

C2. Vậy ta có phương trình:

0=n

C 1

(cid:0)

T(n)

n C1)T(n

(cid:0) (cid:0) (cid:0) (cid:0) (cid:0)

49

Giải thuật MergeSort Giải thuật MergeSort

List MergeSort (List L; int n){ List L1,L2 if (n==1) RETURN(L); else {

Chia đôi L thành L1 và L2, với độ dài n/2; RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2)));

}; };  Hàm MergeSort nhận một danh sách có độ dài n và trả về một

danh sách đã được sắp xếp.

 Thủ tục Merge nhận hai danh sách đã được sắp L1 và L2 mỗi danh sách có độ dài n/2, trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự.

50

Mô hình minh hoạ Mergesort Mô hình minh hoạ Mergesort

Sắp xếp danh sách L gồm 8 phần tử 7, 4, 8, 9, 3, 1, 6, 2

7 4 8 9 3 1 6 2

7 4 8 9

3 1 6 2

8 9

6 2

7 4

3 1

8 9

1 3

4 7

2 6

4 7 8 9

1 2 3 6

1 2 3 4 6 7 8 9

51

Phương trình đệ quy của giải thuật MergeSort Phương trình đệ quy của giải thuật MergeSort

Gọi T(n) là thời gian thực hiện MergeSort một danh

sách n phần tử

Thì T(n/2) là thời gian thực hiện MergeSort một danh

sách n/2 phần tử.

Khi L có độ dài 1 (n = 1) thì chương trình chỉ làm một việc duy nhất là return(L), việc này tốn O(1) = C1 thời gian.

Trong trường hợp n > 1, chương trình phải thực hiện gọi đệ quy MergeSort hai lần cho L1 và L2 với độ dài n/2 do đó thời gian để gọi hai lần đệ quy này là 2T(n/2).