DATA STRUCTURE AND ALGORITHM
1. INTRODUCTION
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
1. GIỚI THIỆU
Dr. Dao Nam Anh

Data Structure and Algorithm

1


Outline – Nội dung

•
•
•
•
•
•

Giải thuật
Dữ liệu
Quan hệ Dữ liệu – Giải thuật
Đánh giá độ phức tạp của giải thuật
Đánh giá độ phức tạp dữ liệu
Ký hiệu độ phức tạp

Data Structure and Algorithm

2


Algorithm

Kết quả phụ
thuộc dữ liệu
đầu vào

Simonas Šaltenis slide
Data Structure and Algorithm

4


Algorithm – Giải thuật
Wiki:

•

Thuật toán, còn gọi là giải thuật, là một tập hợp hữu
hạn của các chỉ thị hay phương cách được định
nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một
trạng thái ban đầu cho trước; khi các chỉ thị này được
áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như
đã dự đoán.

•

Thuật toán là một bộ các qui tắc hay qui trình cụ thể
nhằm giải quyết một vấn đề trong một số bước hữu
hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp
của các dữ kiện đưa vào.

trong tập hợp các số thực có thể là một bộ các bước sau
đây:
Nếu a = 0
b = c thì P(x) có nghiệm bất kì
b ≠ c thì P(c) vô nghiệm
Nếu a ≠ 0
P(x) có duy nhất một
nghiệm x = (c - b)/a
Data Structure and Algorithm

7


Algorithm – Giải thuật
Mục đích thiết kế Giải thuật

Mục đích triển khai

Chạy được cả khi
đầu vào có lỗi

Đúng

Thích ứng

Hiệu quả

Tái sử dụng

Simonas Šaltenis slide

9


Algorithm – Giải thuật
Ví dụ: Sắp xếp
Kết quả

Đầu vào

Dãy số theo thứ tự lớn dần

Dãy số nguyên

a1, a2, a3,….,an
2

5

4

10

7

Tính đúng đắn:
• b1 < b2 < b3 < …. < bn

Sort

b1,b2,b3,….,bn

6

8

9

1

7

2
j

5 1
n

i
Chiến lược
• Bắt đầu từ phần bên đã xếp bên trái
trống”
• Chèn vào bên phải phần đã xếp
• Thực hiện đến khi đúng thứ tự

for j=2 to length(A)
do key=A[j]
“chèn A[j] vào phần đã
sắp xếp A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]

n

i
Chiến lược
• Bắt đầu từ phần bên đã xếp bên trái
trống”
• Chèn vào bên phải phần đã xếp
• Thực hiện đến khi đúng thứ tự

for j=2 to length(A)
do key=A[j]
“chèn A[j] vào phần đã
sắp xếp A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key

Data Structure and Algorithm

12


Algorithm – Giải thuật
Insertion Sort

A

3


while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key

Data Structure and Algorithm

13


Algorithm – Giải thuật
Insertion Sort

A

3

4

6

8

7

1

9

2
j

3

4

6

8

7

1

9

2
j

5 1
n

i
Chiến lược
• Bắt đầu từ phần bên đã xếp bên trái
trống”
• Chèn vào bên phải phần đã xếp
• Thực hiện đến khi đúng thứ tự

for j=2 to length(A)
do key=A[j]
“chèn A[j] vào phần đã

2
j

5 1
n

i
Chiến lược
• Bắt đầu từ phần bên đã xếp bên trái
trống”
• Chèn vào bên phải phần đã xếp
• Thực hiện đến khi đúng thứ tự

for j=2 to length(A)
do key=A[j]
“chèn A[j] vào phần đã
sắp xếp A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key

Data Structure and Algorithm

16


Algorithm – Giải thuật
Insertion Sort


do key=A[j]
“chèn A[j] vào phần đã
sắp xếp A[1..j-1]”
i=j-1
while i>0 and A[i]>key
do A[i+1]=A[i]
i-A[i+1]:=key

Data Structure and Algorithm

17


Algorithm – Giải thuật
Insertion Sort

A

3

4

6

7

8

1


Insertion Sort

A

3

4

6

7

8

9

2

5 1

3

4

6

7

8


8

2

9

5 1

3

4

6

7

8

2

9

5 1

3

4

6



Cấu trúc dữ liệu

•

Khi giải một bài toán, ta cần phải định nghĩa tập
hợp dữ liệu để biểu diễn tình trạng cụ thể. Việc
lựa chọn này tuỳ thuộc vào vấn đề cần giải quyết
và những thao tác sẽ tiến hành trên dữ liệu vào.

•

Có những thuật toán chỉ thích ứng với một cách
tổ chức dữ liệu nhất định, đối với những cách tổ
chức dữ liệu khác thì sẽ kém hiệu quả hoặc không
thể thực hiện được. Chính vì vậy nên bước xây
dựng cấu trúc dữ liệu không thể tách rời bước tìm
kiếm thuật toán giải quyết vấn đề.
Data Structure and Algorithm

20


Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu

•

Cấu trúc dữ liệu trước hết phải biểu diễn được
đầy đủ các thông tin nhập và xuất của bài toán


Việc tổ chức dữ liệu như thế nào có ảnh hưởng rất
lớn đến cách thức xử lý dữ liệu đó cũng như tốc
độ thực thi và sự chiếm dụng bộ nhớ của chương
trình.

Data Structure and Algorithm

22


Cấu trúc dữ liệu

•

Việc đặc tả bằng các cấu trúc tổng quát (generic
structures) và các kiểu dữ liệu trừu tượng
(abstract data types) còn cho phép người lập trình
có thể dễ dàng hình dung ra các công việc cụ thể
và giảm bớt công sức trong việc chỉnh sửa, nâng
cấp và sử dụng lại các thiết kế đã có.

Data Structure and Algorithm

23


Kiểu dữ liệu cơ bản

•


Structure
•Structure
(struct)

•Queue

State
Structure

•Stack

Nor Bahiah Hj Ahmad, Software Engineering Department, FSKSM, UTM
Data Structure and Algorithm

25