Bài giảng Thiết kế và đánh giá thuật toán: Phân tích thuật toán

Thiết Kế & Đánh Giá Thuật Toán Phân Tích Thuật Toán

TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN

(cid:1) Thuật toán

(cid:1) Bài toán sắp xếp

(cid:1) Sắp xếp chèn

(cid:1) Phân tích thời gian chạy sắp xếp chèn

Nội Dung

(cid:1) Một thủ tục tính toán được định nghĩa rõ ràng (cid:1) Một chuỗi các bước tính toán (cid:1) Nhận một tập các giá trị đầu vào (cid:1) Trả một tập các giá trị đầu ra (cid:1) Tính đúng đắn: với tất cả các tập giá trị đầu

vào, thuật toán đưa ra tập giá trị đầu ra đúng

Thuật Toán

(cid:1) Sắp xếp (cid:1) Tìm kiếm (cid:1) Mạng Internet (Định tuyến dữ liệu) (cid:1) Thương mại điện tử (cid:1) Doanh nghiệp sản xuất (cid:1) Đường đi ngắn nhất (cid:1) Chuỗi chung dài nhất (cid:1) Vân vân …

Bài Toán

(cid:1) Cấu trúc dữ liệu

(cid:1) Cách lưu trữ và tổ chức dữ liệu tạo điều kiện truy

cập và thay đổi một cách dễ dàng

(cid:1) Hiệu quả:

(cid:1) P: thuật toán có thể chạy trong thời gian đa thức (cid:1) NP-complete: không thể chạy trong khoảng thời gian

hợp lý (cid:1) Song song:

(cid:1) Nhiều phép tính mỗi giây bằng nhiều lõi

Một Số Vấn Đề Khác

(cid:7) sao

(cid:7) , … , (cid:1)(cid:6)

(cid:7) , (cid:1)(cid:4)

(cid:1) Input: một dãy số (cid:1)(cid:2), (cid:1)(cid:4), … , (cid:1)(cid:6) (cid:1) Output: tổ hợp của dãy trên (cid:1)(cid:2) (cid:7) ≤ ⋯ ≤ (cid:1)(cid:6) (cid:7)

(cid:7) ≤ (cid:1)(cid:4)

cho (cid:1)(cid:2) (cid:1) Ví dụ:

(cid:1) Input: 8 2 4 9 3 6 (cid:1) Output: 2 3 4 6 8 9

(cid:1) Hiệu quả:

(cid:1) Thời gian chạy của thuật toán sắp xếp dãy số? (cid:1) Thuật toán tốt nhất (chạy nhanh nhất)?

Bài Toán Sắp Xếp

(cid:1) Sắp xếp chèn:

(cid:25)(cid:26)é(cid:25) (cid:28)í(cid:30)(cid:26)

(cid:4) (cid:2)(cid:21)(cid:22) (cid:23) (cid:2)(cid:21)(cid:31) (cid:25)(cid:26)é(cid:25) (cid:28)í(cid:30)(cid:26)/"#â% = 20.000 giây ≈ 5,5 giờ

(cid:1) Sắp xếp trộn:

≈ 1.163 giây < 20 phút

*(cid:21) . (cid:2)(cid:21)(cid:22) . +," (cid:2)(cid:21)(cid:22)(cid:25)(cid:26)é(cid:25) (cid:28)í(cid:30)(cid:26) (cid:2)(cid:21)(cid:22) (cid:25)(cid:26)é(cid:25) (cid:28)í(cid:30)(cid:26)/"#â%

(cid:1) Khi nào s.x. chèn nhanh hơn s.x. trộn?

Thuật Toán Sắp Xếp (cid:1) Sắp xếp chèn (Insertion sort): (cid:10)(cid:2)(cid:11)(cid:4) (cid:1) Sắp xếp trộn (Merge sort): (cid:10)(cid:4)(cid:11) log (cid:11) (cid:1) Với (cid:10)(cid:2) = 2; (cid:10)(cid:4) = 50; (cid:11) = 10.000.000

Sắp Xếp Chèn – Minh Họa

8 2

4 9 3 6

2 8 4

9 3 6

2 4 8 9

3 6

2 4 8 9 3

6 2 3 4 8 9 6

2 3 4 6 8 9

>:? ← 5[7] B ← 7 − 1

Sắp Xếp Chèn – Mã Giả

InsertionSort (5) 1 for 7 ← 2 to 5. 9:(cid:11);<= do 2 3 4 while B > 0 and 5 B > >:? do 5 5 B + 1 ← 5[B] 6 B ← B − 1 7 5 B + 1 ← >:?

Mã giả xem tr.18, tr.20 – 22

(cid:1) Khái niệm tính bất biến (loop invariant):

(cid:1) Bắt đầu mỗi vòng lặp for dãy con 5[1 … 7 − 1] chính

là dãy ban đầu nhưng đã được sắp xếp.

(cid:1) Khởi tạo: đúng trước khi vòng for lặp bắt đầu (cid:1) Duy trì: đúng trước một lần lặp thì đúng trước

lần lặp tiếp theo

(cid:1) Kết thúc: tính bất biến giúp chứng minh thuật

toán đúng

Sắp Xếp Chèn – Tính Đúng Đắn

(cid:1) Trường hợp cơ bản (base case) (cid:1) Trường hợp quy nạp (inductive case) (cid:1) Chứng minh tính “Duy trì” sử dụng chứng

Chứng Minh Quy Nạp – Induction Proof

minh quy nạp: (cid:1) Cho rằng 5[1 … > − 1] đã được sắp xếp (cid:1) Chỉ ra 5[1 … >] cũng được sắp xếp (cid:1) Xem chứng minh tr.19 – 20

(cid:1) Kiến trúc Random Access Machine

(cid:1) Xử lý tuần tự các phép toán (cid:1) Các phép toán (thao tác) cơ bản

, …

, =, +, -, *, /, %, load, store, copy, … điều khiển, rẽ nhánh, …

(cid:1) Mỗi phép toán thực hiện trong thời gian cố định (cid:10) (cận trên) (cid:1) Dữ liệu đầu vào (cid:11) được biểu diễn (cid:10) log (cid:11) bit (cid:1) Không bộ nhớ ảo, cache

Phân Tích Thuật Toán – Giả Định

(cid:1) Thời gian chạy phụ thuộc vào dữ liệu đầu vào: dãy đã sắp xếp ≠ dãy chưa sắp xếp

(cid:1) Thời gian chạy phụ thuộc vào độ lớn dữ

Phân Tích Thuật Toán – Thời Gian Chạy

(cid:1) Thông thường xét cận trên (trường hợp

liệu đầu vào: dãy ngắn ≠ dãy dài

xấu nhất)

(cid:1) Trường hợp xấu nhất: (thông thường)

(cid:1)

F((cid:11)) = thời gian lâu nhất thuật toán chạy với dữ liệu đầu vào cỡ (cid:11) bất kỳ

(cid:1) Trường hợp trung bình: (đôi khi)

(cid:1)

F((cid:11)) = thời gian trung bình thuật toán chạy với tất cả dữ liệu đầu vào

(cid:1) Cần giả thiết về hàm phân phối xác xuất cho dữ liệu

đầu vào

(cid:1) Trường hợp tốt nhất: (hiếm)

(cid:1) Lợi dụng thuật toán chậm chạy nhanh với một số dữ

liệu đầu vào

Phân Tích Thuật Toán – Thời Gian Chạy

>:? ← 5[7] B ← 7 − 1

Mã giả xem tr.18, tr.20 – 22

Sắp Xếp Chèn – Mã Giả InsertionSort (5) 1 for 7 ← 2 to 5. 9:(cid:11);<= do 2 3 4 while B > 0 and 5 B > >:? do 5 5 B + 1 ← 5[B] 6 B ← B − 1 7 5 B + 1 ← >:?

Sắp Xếp Chèn – Phân Tích Thời Gian

InsertionSort (5) 1

(cid:11)

for 7 ← 2 to 5. 9:(cid:11);<= do

(cid:11) − 1

>:? ← 5[7]

(cid:11) − 1

B ← 7 − 1

(cid:10)(cid:2) (cid:10)(cid:4) (cid:10)G

(cid:6)

while B > 0 and 5 B > >:? do

(cid:10)H I

JK(cid:4)

5 B + 1 ← 5[B]

B ← B − 1

(cid:6) (cid:10)* I

(cid:11)

5 B + 1 ← >:?

(cid:10)M

(cid:1) Tổng thời gian:

F (cid:11)

(cid:6)

= (cid:10)(cid:2)(cid:11) + (cid:10)(cid:4) (cid:11) − 1 + (cid:10)G (cid:11) − 1 + (cid:10)H I

JK(cid:4)

(cid:6)

+ (cid:10)* I

+ (cid:10)L I

+ (cid:10)M (cid:11) − 1

(cid:1)

Sắp Xếp Chèn – Phân Tích Thời Gian

: số lần lặp vòng while

(cid:1) Trường hợp tốt nhất (

Sắp Xếp Chèn – Phân Tích Thời Gian

F (cid:11)

(cid:1)

F (cid:11) hàm tuyến tính

(cid:1) Khi mảng đã sắp xếp tăng dần

= (cid:10)(cid:2)(cid:11) + (cid:10)(cid:4) (cid:11) − 1 + (cid:10)G (cid:11) − 1 + (cid:10)H (cid:11) − 1 + (cid:10)M (cid:11) − 1 = (cid:10)(cid:2) + (cid:10)(cid:4) + (cid:10)G + (cid:10)H + (cid:10)M (cid:11) + N = (cid:1)(cid:11) + N

(cid:1) Trường hợp xấu nhất

F (cid:11)

= (cid:10)(cid:2)(cid:11) + (cid:10)(cid:4) (cid:11) − 1 + (cid:10)G (cid:11) − 1

+ (cid:10)H

− 1 + (cid:10)*

(cid:11) (cid:11) − 1 2

+ (cid:10)L

+ (cid:10)M (cid:11) − 1

(cid:11) (cid:11) + 1 2 (cid:11) (cid:11) − 1 2

= … (cid:11)(cid:4) + … (cid:11) + … = (cid:1)(cid:11)(cid:4) + N(cid:11) + (cid:10)

(cid:1)

F (cid:11) hàm bậc hai

(cid:1) Khi mảng đã sắp xếp giảm dần

Sắp Xếp Chèn – Phân Tích Thời Gian

(cid:1) Exercise: 2.1-4 tr.22

(cid:1) Cộng 2 số n-bit

(cid:1) Exercise: 2.2-2 tr.29

(cid:1) Sắp xếp lựa chọn (selection sort)

(cid:1) Problem: 2-2 tr.40

(cid:1) Sắp xếp nổi bọt (bubble sort)

Bài Tập

Bài Tập – Exercise 2.1-4

mảng n-phần tử A & B. Tổng 2 số này lưu trong mảng n+1-phần tử C dưới dạng nhị phân. (cid:1) Viết mã giả cho thuật toán cộng 2 số này. (cid:1) Phân tích độ phức tạp của thuật toán.

Cộng 2 số n-bit: (cid:1) Cho 2 số nguyên nhị phân n-bit, lưu trong 2

P 7 + 1 ← 5 7 + O 7 + Q:RB(cid:11)S:Q Q:RB(cid:11)S:Q ← P 7 + 1 div 2 P 7 + 1 ← P 7 + 1 mod 2

P 1 ← Q:RB(cid:11)S:Q

Thời gian chạy:

F (cid:11) = (cid:10)(cid:2) + (cid:10)(cid:4) (cid:11) + 1 + (cid:10)G(cid:11) + (cid:10)H(cid:11) + (cid:10)*(cid:11) + (cid:10)L

= (cid:10)(cid:4) + (cid:10)G + (cid:10)H + (cid:10)* (cid:11) + N = (cid:1)(cid:11) + N

Bài Tập – Exercise 2.1-4 BinaryAdder (5, O, P, (cid:11)) 1 Q:RB(cid:11)S:Q ← 0 2 for 7 ← (cid:11) downto 1 do 3 4 5 6

Bài Tập – Exercise 2.2-2

tử nhỏ nhất của A và đổi chỗ với A[1]. Tìm phần tử nhỏ nhất thứ hai của A và đổi chỗ với A[2]. Tiếp tục như vậy cho n-1 phần tử đầu tiên của A.

(cid:1) Viết mã giả cho thuật toán trên. (cid:1) Tính bất biến (loop invariant) của thuật toán? (cid:1) Tại sao chỉ cần chạy với n-1 phần tử đầu tiên. (cid:1) Phân tích độ phức tạp của thuật toán (trường

hợp tốt nhất & xấu nhất)

Sắp xếp lựa chọn (selection sort): (cid:1) Sắp xếp n số trong mảng A theo cách tìm phần

WR(cid:1)99:W< ← B

if 5 7 < 5[WR(cid:1)99:W<] WR(cid:1)99:W< ← 7

Bài Tập – Exercise 2.2-2 SelectionSort (5) 1 for B ← 1 to 5. 9:(cid:11);<= − 1 do 2 3 for 7 ← B + 1 to 5. 9:(cid:11);<= do 4 5 6 exchange 5 B with 5[WR(cid:1)99:W<]

F (cid:11)

(cid:6)

= (cid:10)(cid:2)(cid:11) + (cid:10)(cid:4) (cid:11) − 1 + (cid:10)G I

+ (cid:10)H I

JK(cid:4)

(cid:6)

+ (cid:10)* I

+ (cid:10)L I

= … (cid:11)(cid:4) + … (cid:11) + … = (cid:1)(cid:11)(cid:4) + N(cid:11) + (cid:10)

Bài Tập – Exercise 2.2-2 SelectionSort (5) Thời gian chạy:

(cid:1) Sắp xếp nổi bọt (bubble sort):

Bài Tập – Problem 2-2

:X(cid:10)= ← Y(cid:1)9W:

Bài Tập – Problem 2-2 BubbleSort (5) 1 do 2 3 for 7 ← 5. 9:(cid:11);<= downto 2 do 4 if 5 7 < 5[7 − 1] 5 exchange 5 7 with 5 7 − 1 6 :X(cid:10)= ←

Bài Tập – Problem 2-2 BubbleSort (5) 1 for B ← 1 to 5. 9:(cid:11);<= − 1 do 2 for 7 ← 5. 9:(cid:11);<= downto B + 1 do 3 if 5 7 < 5[7 − 1] 4 exchange 5 7 with 5[7 − 1]

(cid:1) Phân tích thời gian chạy dựa trên độ lớn

Tổng Kết

(cid:1) Phân tích thời gian chạy thuật toán trong

dữ liệu đầu vào

(cid:1) Thời gian chạy của sắp xếp chèn là hàm bậc hai đối với độ lớn dữ liệu đầu vào

trường hợp xấu nhất