Phân tích thiết kế thuật giải - Độ phức tạp của giải thuật

ĐỘ PHỨC TẠP CỦA GIẢI THUẬT NGÔ QUỐC VIỆT 2014 PHÂN TÍCH THIẾT KẾ THUẬT GIẢI Nội dung 1. Giới thiệu 2. Xác định độ phức tạp 3. Bài tập 4. Hỏi đáp. N g ô Q u ố c V iệ t 2 Ví dụ: thuật giải tìm tuyến tính 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 N g ô Q u ố c V iệ t 3 Ví dụ: tìm nhị phân N g ô Q u ố c V iệ t a c d f g h j l m o p r s u v x z Tìm nhị phân ký tự ‘j’ Phần tử giữa Khoảng tìm 4 Ví dụ: tìm nhị phân N g ô Q u ố c V iệ t a c d f g h j l m o p r s u v x z Phần tử giữa Khoảng tìm Tìm nhị phân ký tự ‘j’ 5 Ví dụ: tìm nhị phân N g ô Q u ố c V iệ t a c d f g h j l m o p r s u v x z center element search interval Tìm nhị phân ký tự ‘j’ 6 Ví dụ: tìm nhị phân N g ô Q u ố c V iệ t a c d f g h j l m o p r s u v x z Phần tử giữa Khoảng tìm Tìm nhị phân ký tự ‘j’ 7 Ví dụ: tìm nhị phân N g ô Q u ố c V iệ t a c d f g h j l m o p r s u v x z Phần tử giữa Khoảng tìm OK Tìm nhị phân ký tự ‘j’ 8 Tìm nhị phân-thuật giải 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 m = (i + j)/2 if x > am ) i = m + 1 else j = m 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 = 𝑛 2𝑘 ⇒ 𝑘 = 𝑙𝑜𝑔2𝑛 N g ô Q u ố c V iệ t 9 Độ 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. • 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). N g ô Q u ố c V iệ t 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á. • 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. N g ô Q u ố c V iệ t 11 Định nghĩa O “lớn” • Định nghĩa: 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). • Chú ý: 𝑂(𝐶. 𝑓(𝑛)) = 𝑂(𝑓(𝑛)) với C là hằng số. Ðặc biệt 𝑂(𝐶) = 𝑂(1). N g ô Q u ố c V iệ t 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 𝑓(𝑛). • Xác định được hằng C sao cho 𝑓(𝑛)  𝐶𝑔(𝑛) khi 𝑛 > 𝑘. • Mục tiêu là tìm cận trên nhỏ nhất 𝑔(𝑛) sao cho 𝑓(𝑛)  𝐶𝑔(𝑛) khi 𝑛 > 𝑘 N g ô Q u ố c V iệ t 13 O lớn Cho 𝑓 𝑛 = 𝑛2 + 2𝑛 + 1. Chứng minh 𝑓(𝑛) là 𝑂 𝑛2 𝑛2 + 2𝑛 + 1 ≤ 4𝑛2. Chọn 𝑘 = 1, 𝐶 = 4, 𝑓 𝑛 ≤ 4. 𝑛2, ∀𝑛 ≥ 1 ⇒ 𝑓(𝑛) là 𝑂 𝑛2 N g ô Q u ố c V iệ t 14 Các tính chất O “lớn” • Định lý: Cho đa thức với ai hằng số, ad > 0, thì N g ô Q u ố c V iệ t    d i i inanf 0 )( )()( dnOnT  15 Một số tính chất của O lớn N g ô Q u ố c V iệ t Quy tắc nhân: Thời gian thực hiện của đoạn hai đoạn chương trình lồng nhau là: 𝑻(𝒏) = 𝑶(𝒇(𝒏). 𝒈(𝒏)) 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 (𝒇(𝒏), 𝒈(𝒏))) QUI TẮC 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 (𝑓(𝑛), 𝑔(𝑛))). • Chứng minh: 𝑇1(𝑛) = 𝑂(𝑓(𝑛)) nên  𝑛1, 𝑐1 sao cho 𝑇1(𝑛) 𝑛1. 𝑇2(𝑛) = 𝑂(𝑔(𝑛)) nên  𝑛2, 𝑐2 sao cho 𝑇2(𝑛) 𝑛2. Chọn 𝑛0 = max (𝑛1, 𝑛2); 𝑐 = max (𝑐1, 𝑐2) =>  𝑛 > 𝑛0 𝑇1(𝑛) + 𝑇2(𝑛) <= 𝑐1. 𝑓(𝑛) + 𝑐2. 𝑔(𝑛) <= 𝑐. 𝑓(𝑛) + 𝑐. 𝑔(𝑛) < = 2𝑐.max (𝑓(𝑛), 𝑔(𝑛)) 𝑇1(𝑛) + 𝑇2(𝑛) = 𝑂(max (𝑓(𝑛), 𝑔(𝑛))) N g ô Q u ố c V iệ t 17 Quy tắc nhân • Độ phức tạp chương trình P là: 𝑂(𝑓(𝑛)). • Nếu thực hiện P 𝑘(𝑛) lần, với 𝑘(𝑛) = 𝑂(𝑔(𝑛)), thì độ phức tạp là: 𝑂(𝑓(𝑛). 𝑔(𝑛)). • Chứng minh: Thời gian thực hiện 𝑘(𝑛) lần P sẽ là 𝑘(𝑛). 𝑇 (𝑛), theo đn:  𝑛𝑘, 𝑐𝑘 > 0 sao cho 𝑘(𝑛) 𝑛𝑘  𝑛𝑇, 𝑐𝑇 > 0 sao cho T 𝑛 𝑛𝑇 Vậy:  𝑛 >= max (𝑛𝑘, 𝑛𝑇) , ta có 𝑘(𝑛). 𝑇(𝑛) <= 𝑐𝑇. 𝑐𝑘. (𝑔(𝑛). 𝑓(𝑛)) N g ô Q u ố c V iệ t 18 Một số tính chất O lớn N g ô Q u ố c V iệ t 19 Một số hàm độ phức tạp phổ biến n logn nlogn n2 n3 2n 1 2 3 8 16 32 0 1 2 3 4 5 0 2 8 24 64 160 1 4 16 64 256 1024 1 8 64 512 4096 32768 2 4 16 256 65536 2147483648 N g ô Q u ố c V iệ t 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 ≠ 𝑜(𝑛) • 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 N g ô Q u ố c V iệ t 21 Ví dụ về phân tích độ phức tạp • Sắp xếp hoán vị trực tiếp 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]); } N g ô Q u ố c V iệ t )( 2 )1( 1)2()1()( 2nO nn nnnT     22 Ví dụ về phân tích độ phức tạp • Nhân ma trận 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]; } } N g ô Q u ố c V iệ t )()( 3nOnnnnT  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 N g ô Q u ố c V iệ t )()( nOnT  24 Ví dụ về phân tích độ phức tạp • Liệt kê mọi cặp phần tử N g ô Q u ố c V iệ t )()( 2nOnT  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. N g ô Q u ố c V iệ t )()( knOnT  26 Ví dụ so sánh độ phức tạp maxdiff (a1, a2, , an: integers) m = 0 for i = 1 to n-1 for j = i + 1 to n if (|ai – aj| > m) m = |ai – aj| Số phép so sánh: 𝑛 − 1 + 𝑛 − 2 + 𝑛 − 3 + + 1 = 𝑛 – 1 𝑛 2 = 1 2 𝑛2 – 1 2 𝑛 = 𝑂 𝑛2 N g ô Q u ố c V iệ t 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𝑙 = 𝑂(𝑛) 27 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 Ω(𝑔(𝑛)) là tập của các hàm: Ω(𝑔(𝑛)) = *𝑓(𝑛): 𝑐 𝑣à 𝑛0 0 ≤ 𝑐𝑔(𝑛) ≤ 𝑓(𝑛), ∀𝑛 ≥ 𝑛0+ g(n) là biên tiệm cận dưới của f(n). Ký hiệu: 𝑓(𝑛) ∈ Ω(𝑔(𝑛)) •  ngược với O lớn, nghĩa là • 𝑓 𝑥 =  𝑔 𝑥 ⟺ 𝑔 𝑥 = 𝑂 𝑓(𝑥) •  “lớn” chỉ độ phức tạp tối thiểu N g ô Q u ố c V iệ t 28 Một số độ phức tạp khác •  lớn: lân cận trên và dưới, nghĩa là 𝑓 𝑥 = Θ 𝑔 𝑥 ⟺ 𝑓 𝑥 = 𝑂 𝑔 𝑥 ∧ 𝑓 𝑥 = Ω 𝑔 𝑥 • 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) N g ô Q u ố c V iệ t 29 Ví dụ về O-lớn, ,  • Sắp từ nhỏ đến lớn các hàm sau 𝑥 + 𝑠𝑖𝑛𝑥; ln 𝑥 ; 𝑥 + 𝑥; 1 𝑥 ; 13 + 𝑥; 𝑒𝑥; 𝑥𝑒; 𝑥𝑥; 𝑥 + 𝑠𝑖𝑛𝑥 𝑥20 − 101 ; 𝑥𝑙𝑛 𝑥; 𝑥 ln 𝑥 2; 𝑙𝑔2𝑥 Trả lời: 1 𝑥 ; 13 + 1 𝑥 ; ln 𝑥 ; 𝑙𝑔2𝑥; 13 + 𝑥; 𝑥 + 𝑠𝑖𝑛𝑥; 𝑥 + 𝑥; 𝑥𝑙𝑛 𝑥; 𝑥 ln 𝑥 2; 𝑥𝑒; 𝑥 + 𝑠𝑖𝑛𝑥 𝑥20 − 101 ; 𝑒𝑥; 𝑥𝑥 N g ô Q u ố c V iệ t 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 toàn trội (hoặc nhỏ) với các khoảng giá trị n khác nhau • Ví dụ: 𝑓 𝑛 = 𝑥2𝑠𝑖𝑛𝑥 , 𝑔 𝑛 = 5𝑥1.5 N g ô Q u ố c V iệ t 31 Phân tích insertsort for(i=2; i <= n; i ++) { x = a[i]; j = i -1; while( (j > 0) && (x < a[i])) { a[j+1]=a[j]; j --; } a[j+1]=x; } N g ô Q u ố c V iệ t 32 Phân tích insertsort • Trường hợp tốt nhất: 𝐵𝑐𝑜𝑚𝑝 𝑛 = 𝑛 − 1 • Trường hợp xấu nhất: 𝑊𝑐𝑜𝑚𝑝 𝑛 = 𝑖 − 1 = 𝑛(𝑛−1) 2 = 𝑂 𝑛2𝑛𝑖=2 • Trường hợp trung bình: lần duyệt thứ i, có tối đa i vị trí để chèn x  xác suất để chèn x vào một vị trí xác định ở bước i là 1/𝑖. N g ô Q u ố c V iệ t 33 Phân tích insertsort • Số lần so sánh nếu chèn x ở bước i ở vị trí • Số lần lặp ở bước i 1. 1 𝑖 + 2. 1 𝑖 + ⋯+ 𝑖 − 1 1 𝑖 = 1 𝑖 𝑘 𝑖−1 𝑘=1 = 1 𝑖 𝑖 𝑖 − 1 2 = 𝑖 − 1 2 • Số lần lặp cho cả mảng: 𝑖−1 2 𝑛 𝑖=2 = 𝑂 𝑛 2 N g ô Q u ố c V iệ t Vị trí (giá trị j) Số lần so sánh x < a[i] 1 i 2 i-1 3 i-2 ... i-2 2 i-1 1 34 Phân tích SelectionSort for(i=1; i <= n-1; i ++) { x = a[i]; k = i; for( j=i+1; j <= n; j ++) { if(a[j]<x) { k = j; x = a[j]; } } a[k]=a[i]; a[i] = x; } • Ý tưởng thuật giải: với mỗi i, dãy i phần tử là dãy tăng N g ô Q u ố c V iệ t 35 Phân tích SelectionSort • Số phép so sánh a[i] < x: 𝑛 𝑛−1 2 = 𝑂 𝑛2 • Số lệnh gán: • Tốt nhất (các lệnh đỏ): 4 𝑛 − 1 • Xấu nhất (lệnh đỏ và xanh lá): 4 𝑛 − 1 + 2.𝑛 𝑛−1 2 = 𝑂 𝑛2 • Trung bình: số lệnh gán trung bình là: 2. 𝑛 − 𝑖 − 1 2 . Vậy tổng số lệnh gán 𝑛 − 𝑖 − 1 + 4 𝑛 − 1 = 𝑂 𝑛2𝑛−1𝑖=1 N g ô Q u ố c V iệ t 36 Định lý master • Ước lượng độ phức tạp trong các thuật giải chia để trị • Xét thủ tục: Function T( n : size) : if n < 1 exit Do work of amount f(n) T(n/b) T(n/b) ...repeat for a total of a times... T(n/b) end • Khi đó: 𝑇 𝑛 = 𝑎𝑇 𝑛 𝑏 + 𝑓(𝑛), f(n) là chi phí thực hiện ngoài đệ quy. N g ô Q u ố c V iệ t 37 Định lý master • Định lý: giả sử 𝑓(𝑛) = 𝑂 𝑛𝑐 • Case 1: Nếu 𝑐 < 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛 𝑙𝑜𝑔𝑏𝑎 • Case 2: Nếu 𝑐 = 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛 𝑐𝑙𝑜𝑔𝑛 • Case 3: Nếu 𝑐 > 𝑙𝑜𝑔𝑏𝑎 thì 𝑇 𝑛 = Θ 𝑛 𝑐 • Ví dụ: • 𝑇 𝑛 = 8𝑇 𝑛/2 + 1000𝑛2 (trường hợp 𝑐 = 2 < 𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔28 = 3  𝑇 𝑛 = Θ 𝑛 3 • 𝑇 𝑛 = 2𝑇 𝑛/2 + 10𝑛 (trường hợp 𝑐 = 1 = 𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔22 = 1  𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑛 • 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛2 (trường hợp 𝑐 = 2 > 𝑙𝑜𝑔𝑏𝑎 = 𝑙𝑜𝑔22 = 1  𝑇 𝑛 = Θ 𝑛 2 N g ô Q u ố c V iệ t 38 Định lý master • Định lý (Case 1): nếu 𝑓 𝑛 = 𝑂 𝑛𝑙𝑜𝑔𝑏𝑎−𝜀 , 𝜀 > 0, thì 𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑏𝑎 . • Định lý (Case 2): nếu 𝑓(𝑛) = Θ 𝑛𝑙𝑜𝑔𝑏𝑎𝑙𝑜𝑔𝑘𝑛 thì 𝑇 𝑛 = Θ 𝑛𝑙𝑜𝑔𝑏𝑎𝑙𝑜𝑔𝑘+1𝑛 (k thường bằng zero). • Định lý (Case 3): nếu 𝑓(𝑛) = Ω 𝑛𝑙𝑜𝑔𝑏𝑎+𝜀 , và a𝑓 𝑛 𝑏 ≤ 𝑐𝑓 𝑛 , 𝑐 < 1 , thì 𝑇 𝑛 = Θ 𝑓(𝑛) . N g ô Q u ố c V iệ t 39 Bài tập • Xác định độ phức tạp của các biểu 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 + 𝑛/𝑙𝑜𝑔𝑛 N g ô Q u ố c V iệ t – Θ 𝑛2 (case 3) – Θ 𝑛2𝑙𝑜𝑔𝑛 (case 2)) – Θ 2𝑛 (case 3) – 𝑁𝑜𝑡 (a: not const) – Θ 𝑛2 (case 1) – 𝑛 𝑙𝑜𝑔2𝑛 – 𝑁𝑜𝑡 (non-polynomial difference between f(n) and 𝑛𝑙𝑜𝑔𝑏 𝑎 ) 40 Bài tập  𝑇 𝑛 = 2𝑇 𝑛/4 + 𝑛0.51  𝑇 𝑛 = 0.5𝑇 𝑛/2 + 1 𝑛  𝑇 𝑛 = 16𝑇 𝑛/4 + 𝑛!  𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑙𝑜𝑔𝑛  𝑇 𝑛 = 3𝑇 𝑛/2 + 𝑛  𝑇 𝑛 = 3𝑇 𝑛/3 + 𝑛  𝑇 𝑛 = 4𝑇 𝑛/2 + 𝑐𝑛  𝑇 𝑛 = 3𝑇 𝑛/4 + 𝑛𝑙𝑜𝑔𝑛  𝑇 𝑛 = 3𝑇 𝑛/3 + 𝑛/2  𝑇 𝑛 = 6𝑇 𝑛/3 + 𝑛2𝑙𝑜𝑔𝑛  𝑇 𝑛 = 4𝑇 𝑛/2 + 𝑙𝑜𝑔𝑛/𝑛 N g ô Q u ố c V iệ t  Θ 𝑛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) 41 Bài tập • Cho đoạn chương trình N g ô Q u ố c V iệ t 1 sum = 0; i =1; 2 while (i<=n){ 3 j = n – i; 4 while (j<=i){ 5 sum = sum + j; 6 j = j+1; 7 } 8 i = i +1; 9 } 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 Bài tập 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 (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. 5. Đọc thêm và trình bày: thuật giải tìm kiếm Knuth- Morris-Pratt. Phân tích độ phức tạp N g ô Q u ố c V iệ t 43