TAILIEUCHUNG - 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: 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. Sử dụng khái niệm độ phức tạp và ký hiệu ô lớn để đánh giá giải thuật. Đố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. Đố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 . 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 đệ

• Kỹ thuật lập trình
• Kỹ thuật lập trình
• giải thuật
• hướng dẫn giải thuật
• cấu trúc dữ liệu
• lập trình
• kỹ thuật máy tính C
• kỹ thuật lập trình C
• giáo trình kỹ thuật lập trình C
• bài tập kỹ thuật lập trình C
• tài liệu kỹ thuật lập trình C
• chuyên ngành kỹ thuật lập trình
• Bài tập kỹ thuật lập trình
• Tài liệu kỹ thuật lập trình
• Bài giảng kỹ thuật lập trình
• Ưng dụng kỹ thuật lập trình
• Ngôn ngữ C
• kỹ thuật máy tính
• môn kỹ thuật lập trình
• ôn tập kỹ thuật lập trình
• cách học kỹ thuật lập trình
• kiến thức kỹ thuật lập trình
• học môn kỹ thuật lập trình
• Đề thi Kỹ thuật lập trình cơ bản
• Câu hỏi Kỹ thuật lập trình cơ bản
• Luyện thi Kỹ thuật lập trình cơ bản
• Ôn thi Kỹ thuật lập trình cơ bản
• Bài thi Kỹ thuật lập trình cơ bản
• Tài liệu Kỹ thuật lập trình cơ bản
• giáo trình kỹ thuật lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật phần mềm
• chương trình lập trình
• giáo trình lập trình
• lập trình hướng đối tượng
• tài liệu lập trình
• chuyên ngành lập trình
• tổng quan về lập trình
• Tổng quan về kỹ thuật lập trình
• Lập trình tốt
• Nguyên tắc lập trình
• Ngôn ngữ lập trình
• ngôn ngữ C++
• Kỹ thuật lập trình căn bản
• Kỹ thuật lập trình nâng cao
• Lập trình C căn bản
• Lập trình C nâng cao