PHÂN TÍCH THIẾT KẾ THUẬT GIẢI
ĐỘ PHỨC TẠP CỦA GIẢI THUẬT
NGÔ QUỐC VIỆT 2014
Nội dung
Xác định độ phức tạp
1. Giới thiệu 2. 3. Bài tập 4. Hỏi đáp.
t
i
ệ V c ố u Q ô g N
2
Ví dụ: thuật giải tìm tuyến tính
t
i
ệ V c ố u Q ô g N
linear_search(x: integer; a1, a2, …, an: integers) i := 1 while (i n and x ai) i := i + 1 if i n then location := i else location := 0 location = vị trí tìm thấy x, hoặc bằng zero nếu không tìm thấy
3
Ví dụ: tìm nhị phân
Tìm nhị phân ký tự ‘j’
Khoảng tìm
t
i
ệ V c ố u Q ô g N
a c d f g h j l m o p r s u v x z
Phần tử giữa
4
Ví dụ: tìm nhị phân
Tìm nhị phân ký tự ‘j’
Khoảng tìm
t
i
a c d f g h j l m o p r s u v x z
ệ V c ố u Q ô g N
Phần tử giữa
5
Ví dụ: tìm nhị phân
Tìm nhị phân ký tự ‘j’
search interval
t
i
a c d f g h j l m o p r s u v x z
ệ V c ố u Q ô g N
center element
6
Ví dụ: tìm nhị phân
Tìm nhị phân ký tự ‘j’ Khoảng tìm
t
i
a c d f g h j l m o p r s u v x z
ệ V c ố u Q ô g N
Phần tử giữa
7
Ví dụ: tìm nhị phân
Tìm nhị phân ký tự ‘j’
Khoảng tìm
t
i
a c d f g h j l m o p r s u v x z
ệ V c ố u Q ô g N
Phần tử giữa
OK
8
Tìm nhị phân-thuật giải
t
i
ệ V c ố u Q ô g N
m = (i + j)/2 if x > am ) i = m + 1 else j = m
procedure binary_search(int x, int a1, a2, …, an) i = 1 // i is left endpoint of search interval j = n // j is right endpoint of search interval while (i < j) begin end if x == ai then location = i else location = 0 Độ phức tạp tìm nhị phân: 𝑶 𝒍𝒐𝒈𝒏 ≪ 𝒏. Hướng dẫn: cần chia n cho 2 bao nhiêu lần để có được mảng 1 phần tử.
1 =
9
𝑛 2𝑘 ⇒ 𝑘 = 𝑙𝑜𝑔2𝑛
Độ phức tạp
• Hai ví dụ về tìm kiếm trên có số lần lặp khác
nhau.
• Thuật giải A cần chạy 5000𝑛 lần (vd: lệnh so
sánh), trong khi B là 1.1 𝑛 lần.
t
i
ệ V c ố u Q ô g N
• Với 𝑛 = 10, B hiệu quả hơn A, khi 𝑛 = 1000, A cần 5.000.000 lần chạy, nhưng B cần 2.5. 1041 lần
• Số lần thực hiện với 𝑛 input được gọi là độ phức
tạp thuật giải được biểu diễn hàm T(n).
10
Giới thiệu
• Yêu cầu cần phải có thuật giải chính xác và nhanh
cần có tiêu chuẩn đánh giá.
t
i
ệ V c ố u Q ô g N
• Một yếu tố quan trọng nhất ảnh hưởng đến tốc độ là kích thước dữ liệu cần xử lý. Nếu n là kích thước đầu vào cần tìm hàm T(n) thể hiện độ phức tạp. Hàm T(n) gọi là độ phức tạp của giải thuật.
• Các yếu tố khác như: phần cứng, ngôn ngữ lập
trình, v.v.. được bỏ qua khi xét độ phức tạp.
11
Định nghĩa O “lớn”
• Định nghĩa:
t
i
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 𝑇(𝑛) ≤ 𝐶𝑓(𝑛) 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à 𝑂(𝑓(𝑛)) (đọc là “ô của f(n)”). • Ví dụ: 𝑇(𝑛) = (𝑛 + 1)2 có tỷ suất tăng là 𝑛2 nên
𝑇(𝑛) = (𝑛 + 1)2 là 𝑂(𝑛2).
ệ V c ố u Q ô g N
• Chú ý: 𝑂(𝐶. 𝑓(𝑛)) = 𝑂(𝑓(𝑛)) với C là hằng số.
Ðặc biệt 𝑂(𝐶) = 𝑂(1).
12
O lớn
• Ý tưởng của big-O là tìm cận trên của độ tăng
trưởng của hàm 𝑓(𝑛) khi n đủ lớn.
• Cận trên xác định bởi hàm 𝑔(𝑛) đơn giản hơn
𝑓(𝑛).
t
i
• Xác định được hằng C sao cho 𝑓(𝑛) 𝐶𝑔(𝑛)
khi 𝑛 > 𝑘.
ệ V c ố u Q ô g N
• Mục tiêu là tìm cận trên nhỏ nhất 𝑔(𝑛) sao cho
𝑓(𝑛) 𝐶𝑔(𝑛) khi 𝑛 > 𝑘
13
O lớn
t
i
Cho 𝑓 𝑛 = 𝑛2 + 2𝑛 + 1. Chứng minh 𝑓(𝑛) là 𝑂 𝑛2 𝑛2 + 2𝑛 + 1 ≤ 4𝑛2. Chọn 𝑘 = 1, 𝐶 = 4, 𝑓 𝑛 ≤ 4. 𝑛2, ∀𝑛 ≥ 1 ⇒ 𝑓(𝑛) là 𝑂 𝑛2
ệ V c ố u Q ô g N
14
Các tính chất O “lớn”
• Định lý: Cho đa thức
t
với ai hằng số, ad > 0, thì
i
ệ V c ố u Q ô g N
15
Một số tính chất của O lớn
t
i
ệ V c ố u Q ô g N
trình
QUI TẮC
Quy tắc tổng: Thời gian thực hiện của đoạn hai chương trình nối tiếp nhau là 𝑻(𝒏) = 𝑶(max (𝒇(𝒏), 𝒈(𝒏)))
Quy tắc nhân: Thời gian thực hiện của đoạn hai đoạn chương lồng nhau là: 𝑻(𝒏) = 𝑶(𝒇(𝒏). 𝒈(𝒏))
16
Quy tắc tổng
• Độ phức tạp chương trình P1 là: 𝑂(𝑓(𝑛)). • Độ phức tạp chương trình P2 là: 𝑂(𝑔(𝑛)). • Thời gian thực hiện tuần tự P1, P2 là:
𝑂(max (𝑓(𝑛), 𝑔(𝑛))).
t
i
• Chứng minh:
ệ V c ố u Q ô g N
𝑛1.
𝑇2(𝑛) = 𝑂(𝑔(𝑛)) nên 𝑛2, 𝑐2 sao cho 𝑇2(𝑛) < 𝑐2. 𝑔(𝑛) ∀𝑛 >
𝑛2.
Chọn 𝑛0 = max (𝑛1, 𝑛2); 𝑐 = max (𝑐1, 𝑐2) => 𝑛 > 𝑛0
𝑇1(𝑛) + 𝑇2(𝑛) <= 𝑐1. 𝑓(𝑛) + 𝑐2. 𝑔(𝑛) <= 𝑐. 𝑓(𝑛) + 𝑐. 𝑔(𝑛) <
= 2𝑐. max (𝑓(𝑛), 𝑔(𝑛))
𝑇1(𝑛) + 𝑇2(𝑛) = 𝑂(max (𝑓(𝑛), 𝑔(𝑛)))
17
𝑇1(𝑛) = 𝑂(𝑓(𝑛)) nên 𝑛1, 𝑐1 sao cho 𝑇1(𝑛) < 𝑐1. 𝑓(𝑛) ∀ 𝑛 >
Quy tắc nhân
phức tạp là: 𝑂(𝑓(𝑛). 𝑔(𝑛)).
t
i
(𝑛), theo đn:
ệ V c ố u Q ô g N
• Độ phức tạp chương trình P là: 𝑂(𝑓(𝑛)). • Nếu thực hiện P 𝑘(𝑛) lần, với 𝑘(𝑛) = 𝑂(𝑔(𝑛)), thì độ
,
ta
có
𝑛 >= max (𝑛𝑘, 𝑛𝑇)
𝑘(𝑛). 𝑇(𝑛) <= 𝑐𝑇. 𝑐𝑘. (𝑔(𝑛). 𝑓(𝑛))
18
• Chứng minh: Thời gian thực hiện 𝑘(𝑛) lần P sẽ là 𝑘(𝑛). 𝑇 𝑛𝑘, 𝑐𝑘 > 0 sao cho 𝑘(𝑛) < 𝑐𝑘. 𝑔(𝑛) ∀𝑛 > 𝑛𝑘 𝑛𝑇, 𝑐𝑇 > 0 sao cho T 𝑛 < 𝑐𝑇. 𝑓 𝑛 ∀𝑛 > 𝑛𝑇 Vậy:
Một số tính chất O lớn
t
i
ệ V c ố u Q ô g N
19
Một số hàm độ phức tạp phổ biến
n
n3
2n
t
i
ệ V c ố u Q ô g N
1 2 3 8 16 32
logn nlogn n2 0 1 2 3 4 5
1 4 16 64 256 1024
0 2 8 24 64 160
1 8 64 512 4096 32768
2 4 16 256 65536 2147483648
20
o nhỏ
• Định nghĩa: 𝑓(𝑛) = 𝑜(𝑔(𝑛)), nghĩa là với mọi 𝑐 > 0 tồn tại 𝑘 > 0 sao cho 0 ≤ 𝑓(𝑛) < 𝑐𝑔(𝑛) với mọi 𝑛 ≥ 𝑘. Giá trị k độc lập n, nhưng có thể phụ thuộc c.
• Ví dụ: 3𝑛 + 4 là 𝑜(𝑛²). Chọn 𝑘 > (3 + √(9 + 16𝑐))/2𝑐.
Trong khi, 3𝑛 + 4 ≠ 𝑜(𝑛)
t
i
• Hàm nếu là o-nhỏ của g cũng là O-lớn của g, nhưng ngược lại
không đúng. o-nhỏ là cận trên, nhưng không nhỏ nhất
ệ V c ố u Q ô g N
21
Ví dụ về phân tích độ phức tạp
• Sắp xếp hoán vị trực tiếp
t
i
ệ V c ố u Q ô g N
22
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]); }
Ví dụ về phân tích độ phức tạp
• Nhân ma trận
t
i
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];
ệ V c ố u Q ô g N
}
void matrixmult(int n, A[][], B[][], C[][]) {
23
}
Ví dụ về phân tích độ phức tạp
• Trộn hai danh sách A=a1,…, an với B=b1,..,bn
t
i
ệ V c ố u Q ô g N
24
Ví dụ về phân tích độ phức tạp
• Liệt kê mọi cặp phần tử
t
i
ệ V c ố u Q ô g N
25
Ví dụ về phân tích độ phức tạp
• Cho đồ thị n node, hãy liệt kê mọi đồ thị con k nút sao cho hai nút không được nối bởi cạnh.
t
i
ệ V c ố u Q ô g N
26
Ví dụ so sánh độ phức tạp
t
i
ệ V c ố u Q ô g N
if (|ai – aj| > m) m = |ai
1 2
1 2
𝑛2 – = maxdiff (a1, a2, …, an: integers) m = 0 for i = 1 to n-1 for j = i + 1 to n – aj| Số phép so sánh: 𝑛 − 1 + 𝑛 − 2 + 𝑛 − 3 + … + 1 = 𝑛 – 1 𝑛 𝑛 = 𝑂 𝑛2 2
27
maxdiff (a1, a2, …, an: integers) min = a1 max = a1 for i = 2 to n if (ai < min) min = ai else (if ai > max) max = ai m = max – min Số phép so sánh: 2𝑛 − 2𝑙 = 𝑂(𝑛)
Một số độ phức tạp khác
• Hai khái niệm tương tự O “lớn” là: “lớn” và
“lớn”.
• Định nghĩa “lớn”: Cho hàm g(n). Ký hiệu
t
i
Ω(𝑔(𝑛)) là tập của các hàm: Ω(𝑔(𝑛)) = *𝑓(𝑛): 𝑐 𝑣à 𝑛0 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛), ∀𝑛
ệ V c ố u Q ô g N
g(n) là biên tiệm cận dưới của f(n). Ký hiệu:
𝑓(𝑛) ∈ Ω(𝑔(𝑛))
≥ 𝑛0+
• 𝑓 𝑥 = 𝑔 𝑥 ⟺ 𝑔 𝑥 = 𝑂 𝑓(𝑥)
• ngược với O lớn, nghĩa là
28
• “lớn” chỉ độ phức tạp tối thiểu
Một số độ phức tạp khác
• lớn: lân cận trên và dưới, nghĩa là 𝑓 𝑥 = Θ 𝑔 𝑥 ⟺ 𝑓 𝑥 = 𝑂 𝑔 𝑥 ∧ 𝑓 𝑥
= Ω 𝑔 𝑥
t
i
• Nhận xét: mọi đa thức là lớn của phần tử có mũ lớn nhất:𝑥4/100000 + 3𝑥3 + 5𝑥2– 9 = Θ(𝑥4)
ệ V c ố u Q ô g N
29
Ví dụ về O-lớn, ,
• Sắp từ nhỏ đến lớn các hàm sau
;
1 𝑥 + 𝑠𝑖𝑛𝑥; ln 𝑥 ; 𝑥 + 𝑥; 𝑥 13 + 𝑥; 𝑒 𝑥; 𝑥𝑒; 𝑥 𝑥; 𝑥 + 𝑠𝑖𝑛𝑥 𝑥20 − 101 ; 𝑥𝑙𝑛 𝑥; 𝑥 ln 𝑥 2; 𝑙𝑔2𝑥
t
i
ệ V c ố u Q ô g N
; ln 𝑥 ; 𝑙𝑔2𝑥; 13 + 𝑥; 𝑥 + 𝑠𝑖𝑛𝑥; 𝑥 +
1 𝑥
Trả lời: 1 ; 13 + 𝑥 𝑥; 𝑥𝑙𝑛 𝑥; 𝑥 ln 𝑥 2; 𝑥𝑒;
𝑥 + 𝑠𝑖𝑛𝑥 𝑥20 − 101 ; 𝑒 𝑥; 𝑥 𝑥
30
Các hàm không so sánh được
• Hai hàm 𝑓(𝑛) và 𝑔(𝑛) gọi là không so sánh được
nếu chúng không là cận (trên hoặc dưới) của nhau
• Thể hiện: độ phức tạp của chúng không hoàn
t
i
toàn trội (hoặc nhỏ) với các khoảng giá trị n khác nhau
ệ V c ố u Q ô g N
• Ví dụ: 𝑓 𝑛 = 𝑥2𝑠𝑖𝑛𝑥 , 𝑔 𝑛 = 5𝑥1.5
31
Phân tích insertsort
t
i
ệ V c ố u Q ô g N
x = a[i]; j = i -1; while( (j > 0) && (x < a[i])) { a[j+1]=a[j]; j --; } a[j+1]=x;
32
for(i=2; i <= n; i ++) { }
Phân tích insertsort
𝑖 − 1 =
= 𝑂 𝑛2
𝑊𝑐𝑜𝑚𝑝 𝑛 =
𝑛 𝑖=2
𝑛(𝑛−1) 2
• Trường hợp tốt nhất: 𝐵𝑐𝑜𝑚𝑝 𝑛 = 𝑛 − 1 • Trường hợp xấu nhất:
t
i
• Trường hợp trung bình: lần duyệt thứ i, có tối đa i vị trí
ệ V c ố u Q ô g N
33
để chèn x xác suất để chèn x vào một vị trí xác định ở bước i là 1/𝑖.
Phân tích insertsort
Vị trí (giá trị j)
Số lần so sánh x < a[i]
1
i
2
i-1
3
i-2
t
i
...
i-2
2
ệ V c ố u Q ô g N
i-1
1
• Số lần so sánh nếu chèn x ở bước i ở vị trí
𝑖−1
1.
+ 2.
+ ⋯ + 𝑖 − 1
=
=
=
1 𝑖
1 𝑖
1 𝑖
1 𝑖
1 𝑖
𝑖 𝑖 − 1 2
𝑖 − 1 2
𝑘 𝑘=1
• Số lần lặp ở bước i
𝑛 𝑖=2
34
= 𝑂 𝑛2 • Số lần lặp cho cả mảng: 𝑖−1 2
Phân tích SelectionSort
t
i
ệ V c ố u Q ô g N
k = j; x = a[j];
x = a[i]; k = i;
for( j=i+1; j <= n; j ++) {
if(a[j] 35 for(i=1; i <= n-1; i ++) {
}
• Ý tưởng thuật giải: với mỗi i, dãy i phần tử là dãy tăng 𝑛 𝑛−1
2 • Số phép so sánh a[i] < x: = 𝑂 𝑛2 • Số lệnh gán: t • Tốt nhất (các lệnh đỏ): 4 𝑛 − 1 i 2.𝑛 𝑛−1
2 = • Xấu nhất (lệnh đỏ và xanh lá): 4 𝑛 − 1 + ệ
V
c
ố
u
Q
ô
g
N 𝑂 𝑛2 • Trung bình: số lệnh gán trung bình là: 2. 𝑛 − 𝑖 − 1 2 . 𝑛−1
𝑖=1 36 Vậy tổng số lệnh gán 𝑛 − 𝑖 − 1 + 4 𝑛 − 1 = 𝑂 𝑛2 • Ước lượng độ phức tạp trong các thuật giải chia để trị
• Xét thủ tục: t i ệ
V
c
ố
u
Q
ô
g
N Do work of amount f(n) • Khi đó: 𝑇 𝑛 = 𝑎𝑇 + 𝑓(𝑛), f(n) là chi phí thực hiện 𝑛
𝑏 37 ngoài đệ quy. • Định lý: giả sử 𝑓(𝑛) = 𝑂 𝑛𝑐 t i • Ví dụ: • 𝑇 𝑛 = 8𝑇 𝑛/2 + 1000𝑛2 (trường hợp 𝑐 = 2 < ệ
V
c
ố
u
Q
ô
g
N • Case 1: Nếu 𝑐 < 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑏𝑎
• Case 2: Nếu 𝑐 = 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛𝑐𝑙𝑜𝑔𝑛
• Case 3: Nếu 𝑐 > 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛𝑐 𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔28 = 3 𝑇 𝑛 = Θ 𝑛3 38 • 𝑇 𝑛 = 2𝑇 𝑛/2 + 10𝑛 (trường hợp 𝑐 = 1 =
𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔22 = 1 𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑛
• 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛2 (trường hợp 𝑐 = 2 >
𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔22 = 1 𝑇 𝑛 = Θ 𝑛2 • Định lý (Case 1): nếu 𝑓 𝑛 = 𝑂 𝑛𝑙𝑜𝑔𝑏𝑎−𝜀 , 𝜀 > 0, thì t i 𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑏𝑎 . ệ
V
c
ố
u
Q
ô
g
N • Định lý (Case 2): nếu 𝑓(𝑛) = Θ 𝑛𝑙𝑜𝑔𝑏𝑎𝑙𝑜𝑔𝑘𝑛 thì
𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑏𝑎𝑙𝑜𝑔𝑘+1𝑛 (k thường bằng zero). 𝑛
𝑏 ≤ • Định lý (Case 3): nếu 𝑓(𝑛) = Ω 𝑛𝑙𝑜𝑔𝑏𝑎+𝜀 , và a𝑓 39 𝑐𝑓 𝑛 , 𝑐 < 1 , thì 𝑇 𝑛 = Θ 𝑓(𝑛) . • Xác định độ phức tạp của các biểu t i ệ
V
c
ố
u
Q
ô
g
N thức sau, hoặc xác định là không thể
áp dụng định lý master.
• 𝑇 𝑛 = 3𝑇 𝑛/2 + 𝑛2
• 𝑇 𝑛 = 4𝑇 𝑛/2 + 𝑛2
• 𝑇 𝑛 = 𝑇 𝑛/2 + 2𝑛
• 𝑇 𝑛 = 2𝑛𝑇 𝑛/2 + 𝑛𝑛
• 𝑇 𝑛 = 16𝑇 𝑛/4 + 𝑛
• 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛𝑙𝑜𝑔𝑛
• 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛/𝑙𝑜𝑔𝑛 – Θ 𝑛2 (case 3)
– Θ 𝑛2𝑙𝑜𝑔𝑛 (case 2))
– Θ 2𝑛 (case 3)
– 𝑁𝑜𝑡 (a: not const)
– Θ 𝑛2 (case 1)
– 𝑛 𝑙𝑜𝑔2𝑛
– 𝑁𝑜𝑡 40 (non-polynomial
difference between f(n)
𝑎
and 𝑛𝑙𝑜𝑔𝑏 ) 𝑇 𝑛 = 2𝑇 𝑛/4 + 𝑛0.51 1
𝑛
𝑇 𝑛 = 16𝑇 𝑛/4 + 𝑛! t i ệ
V
c
ố
u
Q
ô
g
N 𝑇 𝑛 = 0.5𝑇 𝑛/2 + 41 Θ 𝑛0.51 (case 3)
𝑁𝑜𝑡 (a < 1)
Θ 𝑛! (case 3)
Θ 𝑛 (case 1)
Θ 𝑛𝑙𝑜𝑔3 (case 1)
Θ 𝑛 (case 1)
Θ 𝑛2 (case 1)
Θ 𝑛𝑙𝑜𝑔𝑛 (case 3)
Θ 𝑛𝑙𝑜𝑔𝑛 (case 3)
Θ 𝑛2𝑙𝑜𝑔𝑛 (case 2)
Θ 𝑛2 (case 1) 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑙𝑜𝑔𝑛
𝑇 𝑛 = 3𝑇 𝑛/2 + 𝑛
𝑇 𝑛 = 3𝑇 𝑛/3 + 𝑛
𝑇 𝑛 = 4𝑇 𝑛/2 + 𝑐𝑛
𝑇 𝑛 = 3𝑇 𝑛/4 + 𝑛𝑙𝑜𝑔𝑛
𝑇 𝑛 = 3𝑇 𝑛/3 + 𝑛/2
𝑇 𝑛 = 6𝑇 𝑛/3 + 𝑛2𝑙𝑜𝑔𝑛
𝑇 𝑛 = 4𝑇 𝑛/2 + 𝑙𝑜𝑔𝑛/𝑛 • Cho đoạn chương trình t i ệ
V
c
ố
u
Q
ô
g
N 1
2
3
4
5
6
7
8
9 sum = 0; i =1;
while (i<=n){
j = n – i;
while (j<=i){
sum = sum + j;
j = j+1;
}
i = i +1;
} a) Tính số phép gán và phép so sánh được thực hiện trong đoạn chương trình trên b) Tính độ phức tạp 42 𝐼𝑓 𝑓 = 𝑂(𝑔) 𝑎𝑛𝑑 𝑔 = 𝑂() 𝑡𝑒𝑛 𝑓 = 𝑂(). t i 1. Chứng minh tính chất bắc cầu của O lớn
2. Chứng minh các tính chất / quy tắc của O lớn.
3. Phân tích độ phức tạp các giải thuật sắp xếp ệ
V
c
ố
u
Q
ô
g
N (buble sort, quicksort, v.v). 4. Đọc thêm và trình bày: Tìm kiếm chuỗi (tìm chuỗi trong
một chuỗi khác-sử dụng cấu trúc mảng). Phân tích độ
phức tạp. Morris-Pratt. Phân tích độ phức tạp 43 5. Đọc thêm và trình bày: thuật giải tìm kiếm Knuth-Phân tích SelectionSort
Định lý master
Function T( n : size) :
if n < 1 exit
T(n/b)
T(n/b)
...repeat for a total of a times...
T(n/b)
end
Định lý master
Định lý master
Bài tập
Bài tập
Bài tập
Bài tập
![Tài liệu ôn tập môn Lập trình web 1 [mới nhất/chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251208/hongqua8@gmail.com/135x160/8251765185573.jpg)
