Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình - Một số vấn đề về thuật toán - chương 3

Chương 3: Phân tích độ phức tạp thuật toán Chương trước ta quan tâm tới đáp số đúng của thuật toán và cách chứng minh thuật toán đúng. Nhưng thuật toán hiệu quả lại là một vấn đề khác, có thể có những thuật toán đúng nhưng không hiệu quả. Chương này và những chương sau ta xét vấn đề này cho các thuật toán thông dụng nhất hiện nay. | diUVN q 5 PHÂN TÍCH ĐỘ PHỨC TẠP THUẬT TOÁN 3.1. Đánh glâ thuật toán qua phép toán thực hiên.70 3.2. Xác định độ phức tạp tính toán.71 3.3. Đô phức tạp của thuật toán. 75 3.4. Phân tích độ phức tạp thuật toán không hổi quy . 80 3.5. Phân tích thuật toán hổi quy.83 3.6. Bài tập . . . .88 Chương trước ta quan tâm tới đáp số đứng của thuật toán và cạch chứng minh thuật toán đúng. Nhưng thuật toán hiệu quả lại là một vấn đề khác có thể có những thuật toán đúng nhưng không hiệu quả. Chương này và những chương sau ta xét vân đề này cho các thuật toán thông đụng nhất hiên hay. Một thước đo hiệu quả đó là thời gian mà máy tính sử dụng đế giải bài toán theo thuật toán đang xét khi các giá trị đầu vào có một kích thước xầc định. Một thước đo thứ hai ỉà bộ nhớ đòi hỏi để thực hiện thuật toán đó khí giá trị đầu vào có kích thước cho trước. Độ phức tạp tính toán của thuật toán bao gồm những thước đo như vậy để so sánh hiệu qụả thực hiện của thuật toán. Gắn liền với thời gian tính toán của thuật toán ỉà đô phức tập thời gian và với bộ nhớ là độ phức tạp không gian Biết được độ phức tạp mời gian chò một thuật toán là rất quan trọng vì khí đó ta biết đứợc thời gian một phút một năm một tỉ năm để thực hiện thuật toán đó. Độ phức tạp không gian đòi hỏi của thuật toán mà ta biết được thì cho ta một bước chuẩn bị và thấy đựợc khả năng đáp ứng trong viêc tính toán của thuật toán và độ phúc tạp này không thể bỏ qua. Độ phức tạp không gian gắn liền với cấu trúc dữ liệu đặc biệt dùng để tính toán trong thuật toán. Trong tài liệu này chứng ta không nghiên cứu về cơ sỏ dữ liệu nên ta bỏ qua đô phúc tạp không gian. 70 Chương 3 Phân tích độ phức tạp thuật toán 7.1. ĐÁNH GIÃ THUẬT TOÁN OU A PHÉP TOÁN THỤC HIỆN Độ phức tạp thời gian của một thuật toán có thể được xem xét qua các phép toán được dùng với các giá trị đầu vào xác định. Các phép toán được dùng để đo độ phức tạp thời gian cỏ thể là phép so sánh các sô nguyên phép cộng trừ nhân và chia các số nguyên hoặc bất kì một phép toán sơ cấp nào