CSI106 · Nhóm 2

Cấu trúc dữ liệu và thuật toán ảnh hưởng thế nào đến hiệu năng phần mềm?

How Data Structures and Algorithms Affect Real-World Software Performance

Mục lục (Contents)

Phần mềm chạy nhanh hay chậm do đâu?

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

Dữ liệu được tổ chức thế nào

+

Thuật toán(Algorithm)

Dữ liệu được xử lý thế nào

=

Hiệu năng(Performance)

Thời gian chạy (run time) Bộ nhớ (memory)

Thuật toán (Algorithm)

Đầu vào (Input)

Xử lý từng bước (Processing)

Đầu ra (Output)

Ví dụ: tìm số lớn nhất (Find Largest)

12

8

13

9

11

Largest =

–

Nếu số hiện tại > Largest → gán Largest = số hiện tại

Ba cấu trúc cơ bản (Three Basic Constructs)

Tuần tự(Sequence)

Các lệnh chạy lần lượt

Quyết định(Decision)

Kiểm tra điều kiện, chọn nhánh

Lặp(Repetition)

Lặp lại một nhóm lệnh

Vòng lặp chạy n lần → thời gian chạy tăng theo n

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

scores

851

722

903

644

985

Mảng (Array)Cùng kiểu, truy cập bằng chỉ số (index)

student

id2024

nameAn

gradeA

Bản ghi (Record)Nhiều trường (field) khác kiểu

list

12

25

37

Danh sách liên kết (Linked List)Mỗi nút (node) = dữ liệu + liên kết (link)

Ký hiệu Big-O (Big-O Notation)

Đếm số phép toán (operations) theo số đầu vào n

Cùng một bài toán với 1.000.000 đầu vào

Máy tính chạy 1.000.000 lệnh mỗi giây

O(log n)

6 phép toán

6 µs

O(n)

10⁶ phép toán

1 giây

O(n²)

10¹² phép toán

277 giờ

Độ dài thanh theo thang logarit (log scale)

Tìm kiếm (Searching)

Tìm vị trí của giá trị cần tìm (target) trong danh sách

Tìm kiếm tuần tự(Sequential / Linear Search)

10

45

8

2

98

33

Dùng cho mọi danh sách

Tìm kiếm nhị phân(Binary Search)

1

3

5

6

7

8

Danh sách phải được sắp xếp (sorted)

Tìm kiếm tuần tự (Linear Search)

Tìm 98

101

452

83

24

985

336

117

0lần so sánh

nTối đa (worst case)

(n + 1) / 2Trung bình (average)

O(n)Độ phức tạp (complexity)

Tìm kiếm nhị phân (Binary Search)

Tìm 14

Ban đầu

Bước 1

14 > 8 → bỏ nửa trái

Bước 2

Tìm thấy

Tuần tự (Linear): 9 lần

Nhị phân (Binary): 2 lần

Mỗi bước bỏ một nửa → tối đa ≈ log₂n lần · O(log n)

Số lần so sánh tối đa (Worst Case)

Tuần tự (Linear)Nhị phân (Binary)

1.000phần tử

1.000

10

1.000.000phần tử

1.000.000

20

1.000.000.000phần tử

1.000.000.000

30

Ứng dụng thực tế (Real-world Applications)

Danh bạ điện thoại(Phone book)

ABC…

Từ điển(Dictionary)

ABC…

Cơ sở dữ liệu(Database)

123…

Muốn tìm nhanh → dữ liệu cần được sắp xếp trước

Vì sao cần sắp xếp (Sorting)?

Chưa sắp xếp

Minh
An
Tấn
Bảo
Sơn
Hà

Sắp xếp

Đã sắp xếp (A → Z)

An
Bảo
Hà
Minh
Sơn
Tấn

Chỉ tìm tuần tự · O(n)

Tìm nhị phân · O(log n)

Sắp xếp chọn (Selection Sort)

1

Tìm phần tử nhỏ nhấttrong phần chưa sắp xếp

2

Đổi chỗ (swap)với phần tử đầu phần chưa xếp

3

Dời bức tường (wall)sang phải 1 ô

n − 1 lượt · O(n²)

Sắp xếp nổi bọt (Bubble Sort)

1

So sánh 2 phần tử kề nhauđi từ cuối danh sách lên

2

Đổi chỗ nếu sai thứ tựsố nhỏ nhất “nổi” lên đầu

3

Dời bức tường (wall)sang phải 1 ô

n − 1 lượt · O(n²)

Sắp xếp chèn (Insertion Sort)

1

Lấy phần tử đầucủa phần chưa sắp xếp

2

Chèn vào đúng chỗtrong phần đã sắp xếp

Giống cách xếp bài(playing cards)

n − 1 lượt · O(n²)

Sắp xếp 1.000.000 phần tử

Máy tính chạy 1.000.000 phép toán mỗi giây

Chọn · Nổi bọt · Chèn(Selection · Bubble · Insertion)

O(n²)

10¹² phép toán

≈ 277 giờ

Sắp xếp nhanh · Sắp xếp trộn(Quick Sort · Merge Sort)

O(n log n)

≈ 2 × 10⁷ phép toán

≈ 20 giây

3 thuật toán đơn giản là nền tảng (foundation) của các thuật toán nhanh

Mảng (Array)

Các phần tử nằm liền kề nhau trong bộ nhớ (memory)

scores

Lấy phần tử theo chỉ số: 1 bước · O(1)

Chèn vào giữa: dời 5 phần tử · O(n)

Danh sách liên kết (Linked List)

Chèn 30: chỉ đổi 2 liên kết · O(1)

Tìm kiếm: duyệt từ đầu · O(n)

Mảng hay danh sách liên kết?

Thao tác (Operation)

Mảng (Array)

Danh sách liên kết (Linked List)

Lấy phần tử thứ i

1 bước · O(1)

Đi từ đầu · O(n)

Chèn / xóa ở giữa

Dời phần tử · O(n)

Đổi liên kết · O(1)

Tìm kiếm nhị phân

Được (khi đã sắp xếp)

Không

Kích thước (Size)

Cố định (fixed)

Linh hoạt (flexible)

Chọn theo thao tác được dùng nhiều nhất

Ngăn xếp (Stack)

push pop

5

10

15

20

đỉnh (top)

Vào sau – ra trước(LIFO: Last In, First Out)

Vào (push)

5

10

15

20

Ra (pop)

20

15

10

5

Hoàn tác(Undo)

Nút quay lại(Back)

push, pop: 1 bước · O(1)

Hàng đợi (Queue)

dequeueđầu (front)

5

10

15

20

enqueuecuối (rear)

Vào trước – ra trước(FIFO: First In, First Out)

Vào

5

10

15

20

Ra

5

10

15

20

Hàng đợi in(Print queue)

Lập lịch tiến trình của hệ điều hành(Process scheduling)

enqueue, dequeue: 1 bước · O(1)

Cây nhị phân tìm kiếm (Binary Search Tree)

Trái < Gốc < Phải(Left < Root < Right)

Cây cân đối: ≈ log₂n bước · O(log n)

Thư mục(Directory)

Chỉ mục CSDL(Database index)

Đồ thị (Graph)

Đỉnh (vertex)

Cạnh (edge)

5Trọng số (weight): khoảng cách

3 → 2 → 06 + 8 = 14

3 → 1 → 02 + 5 = 7 · đường ngắn nhất (shortest path)

Bản đồ, GPS

Mạng xã hội

Định tuyến (routing)

Băm (Hashing)

Tuần tự (sequential): đọc từ đầu Chỉ mục (indexed): tra chỉ mục Băm (hashed): tính ra địa chỉ

Khóa (key)121267

Hàm băm (hash function)key mod 307 + 1

Địa chỉ (address)003

Bản ghi (record)Bryan Devaux · 11.45

Không cần tìm: ≈ 1 bước · O(1)

Va chạm(Collision)

123013151564 214

Duc LeeRich White

nối bằng danh sách liên kết

Tổng kết (Summary)

Bài toán

Lựa chọn chậm

Lựa chọn nhanh

Tìm 1 phần tử trong 1.000.000

Tuần tự: 1.000.000 lần

Nhị phân, BST: ≈ 20 lần
Băm: ≈ 1 lần

Sắp xếp 1.000.000 phần tử

Chọn, nổi bọt, chèn: ≈ 277 giờ

Quick sort, merge sort: ≈ 20 giây

Chèn liên tục vào giữa

Mảng: dời n phần tử

Danh sách liên kết: đổi 2 liên kết

Lấy phần tử thứ i

Danh sách liên kết: đi i bước

Mảng: 1 bước

Kết luận (Conclusion)

Dữ liệu càng lớn, chênh lệch hiệu năng càng lớn

Không có cấu trúc dữ liệu tốt nhất cho mọi bài toán

Chọn đúng cấu trúc dữ liệu + thuật toán → phần mềm nhanh

Cảm ơn đã lắng nghe

Hỏi & Đáp (Q&A)

Tài liệu: B. Forouzan, Foundations of Computer Science · CSI106, chương 6, 9, 10

Cấu trúc dữ liệu và thuật toán ảnh hưởng thế nào đến hiệu năng phần mềm?

Mục lục (Contents)

Phần mềm chạy nhanh hay chậm do đâu?

Thuật toán (Algorithm)

Ba cấu trúc cơ bản (Three Basic Constructs)

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

Ký hiệu Big-O (Big-O Notation)

Cùng một bài toán với 1.000.000 đầu vào

Tìm kiếm (Searching)

Tìm kiếm tuần tự (Linear Search)

Tìm kiếm nhị phân (Binary Search)

Số lần so sánh tối đa (Worst Case)

Ứng dụng thực tế (Real-world Applications)

Vì sao cần sắp xếp (Sorting)?

Chưa sắp xếp

Đã sắp xếp (A → Z)

Sắp xếp chọn (Selection Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chèn (Insertion Sort)

Sắp xếp 1.000.000 phần tử

Mảng (Array)

Danh sách liên kết (Linked List)

Mảng hay danh sách liên kết?

Ngăn xếp (Stack)

Hàng đợi (Queue)

Cây nhị phân tìm kiếm (Binary Search Tree)

Đồ thị (Graph)

Băm (Hashing)

Va chạm(Collision)

Tổng kết (Summary)

Kết luận (Conclusion)

Cảm ơn đã lắng nghe

Chọn slide · Esc để đóng