tailieunhanh - Bài giảng Thiết kế và đánh giá thuật toán: Chia để trị - TS. Lê Nguyên Khôi

Bài giảng "Thiết kế và đánh giá thuật toán: Chia để trị" trình bày các nội dung: Kỹ thuật thiết kế, sắp xếp gộp, tính lũy thừa, tìm kiếm nhị phân, tính số Fibonacci, tháp Hanoi, nhân ma trận, thuật toán Strassen. . | Thiết Kế & Đánh Giá Thuật Toán Chia Để Trị TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung Kỹ thuật thiết kế Sắp xếp gộp Tính lũy thừa Tìm kiếm nhị phân Tính số Fibonacci Tháp Hanoi Nhân ma trận Thuật toán Strassen 1 Kỹ Thuật Thiết Kế Chia Để Trị Chia bài toán lớn thành các bài toán nhỏ Bài toán nhỏ đơn giản, giải trực tiếp Nếu không tiếp tục chia nhỏ bài toán con Gộp lời giải của các bài toán con 2 Sắp Xếp Gộp (Merge Sort) Chia: chia đôi mảng Trị: Sử dụng đệ quy sắp xếp 2 mảng con Gộp: gộp 2 mảng với thời gian tuyến tính MergeSort ( , 1, ) 1 if = 1 return 2 MergeSort ( , 1, /2 ) 3 MergeSort ( , /2 + 1, ) 4 Merge ( , 1, /2 , /2 + 1, ) ( ) = 2 ( /2) + Θ( ) chia và gộp # bài toán con độ lớn bài toán con 3 Định Lý Tổng Quát – (nhắc lại) = / + ( ) Nếu ∈ ( ) với hằng số > 0 ∈ ( ) 2. Nếu ∈ ( ) ∈ ( log ) 3. Nếu ∈ "( # ) với hằng số > 0 và thỏa mãn / ≤ % ( ) với % < 1 ∈ ( ( )) Sắp xếp gộp: = 2, = 2 ⇒ = ( ) = ⇒ trường hợp 2 ⇒ ( ) ∈ ( log .