Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình giải thuật của Nguyễn Văn Linh part 3

Trong chương này, chúng ta cần phải nắm vững các ý sau: 1.- Sự phân tích, đánh giá giải thuật là cần thiết để lựa chọn giải thuật tốt, hoặc để cải tiến giải thuật. 2.- Sử dụng khái niệm độ phức tạp và ký hiệu ô lớn để đánh giá giải thuật. 3.- Đối với các chương trình không gọi chương trình con, thì dùng quy tắc cộng, quy tắc nhân và quy tắc chung để phân tích, tính độ phức tạp. 4.- Đối với các chương trình gọi chương trình con, thì tính độ phức tạp theo nguyên tắc “từ trong ra” | Giải thuật Kĩ thuật phân tích giải thuật T n T n T n T n T n anlogn - an 2b C2n anlogn b b C2 - a n . Nếu lấy a C2 b ta được anlogn b b C2 - C2 - b n anlogn b 1-n b anlogn b f n . do b 0 và 1-n 0 Nếu ta lấy a và b sao n. Ta phải giải hệ I a cho cả và đều thoả mãn thì T n an logn b với mọi b C1 C 2 b Để đơn giản ta giải hệ - b C1 a C2 b và a C1 C2 ta được T n C1 C2 nlogn C1 với mọi n. Dễ dàng ta có b C1 Hay nói cách khác T n là O nlogn . 1.6.2.3 Lời giải tổng quát cho một lớp các phương trình đệ quy Khi thiết kế các giải thuật người ta thường vận dụng phương pháp chia để trị mà ta sẽ bàn chi tiết hơn trong chương 3. Ở đây chi trình bày tóm tắt phương pháp như sau Để giải một bài toán kích thước n ta chia bài toán đã cho thành a bài toán con mỗi bài toán con có kích thước n. Giải các bài toán con này và tổng hợp kết quả lại để được kết quả của bài toán đã cho. Với các bài toán con chúng ta cũng sẽ áp dụng phương pháp đó để tiếp tục chia nhỏ ra nữa cho đến các bài toán con kích thước 1. Kĩ thuật này sẽ dẫn chúng ta đến một giải thuật đệ quy. Giả thiết rằng mỗi bài toán con kích thước 1 lấy một đơn vị thời gian và thời gian để chia bài toán kích thước n thành các bài toán con kích thước n và tổng hợp kết quả từ các bài toán con để được lời giải của bài toán ban đầu là d n . Chẳng hạn đối với ví dụ MergeSort chúng ta có a b 2 và d n C2n. Xem C1 là một đơn vị . Tất cả các giải thuật đệ quy như trên đều có thể thành lập một phương trinh đệ quy tổng quát chung cho lớp các bài toán ấy. Nếu gọi T n là thời gian để giải bài toán kích thước n thì T -b là thời gian để giải bài toán con kích thước n. Khi n 1 theo giả thiết trên thì thời gian giải bài toán kích thước 1 là 1 đơn vị tức là T 1 1. Khi n lớn hơn 1 ta phải giải đệ quy a bài toán con kích thước mỗi bài toán con tốn T -b nên thời gian cho a lời giải đệ quy này là aT -b- . Ngoài ra ta còn phải tốn thời gian để phân chia bài toán và tổng hợp các kết quả thời gian này theo giả thiết trên là d n . Vậy ta có phương trình đệ