Bài giảng Cấu trúc dữ liệu: Chương 11 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 11: Độ phức tạp (Complexity) trình bày về khái niệm thuật toán, các tính chất cơ bản của thuật toán, độ phức tạp của thuật toán, độ phức tạp về không gian, độ phức tạp về thời gian,..
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Chương 11 - Nguyễn Xuân VinhGV: NGUYỄN XUÂN VINH CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] ĐỘ PHỨC TẠPMÔN: CẤU TRÚC DỮ LIỆU (Complexity) Nguyễn Xuân Vinh nguyenxuanvinh@hcmuaf.edu.6/12/14 vn/XX1GV: NGUYỄN XUÂN VINH Khái niệm • Thuật toán (Algorithm) là một dãy hữu hạn các bước có thể thực thi được mà theo đó ta đạt được lời giải của bài toán. • Từ Algorithm bắt nguồn từ nhà toán học Ả Rập Al-Khwārizmī • Thuật toán giải phương trình bậc 2, thuật toán tìm số lớn nhất trong dãy số, thuật toán sắp xếp…MÔN: CẤU TRÚC DỮ LIỆU6/12/14/XX2GV: NGUYỄN XUÂN VINH Ví dụ • Mô tả giải thuật tìm phần tử lớn nhất trong dãy hữu hạn các phần tử – B1: Đặt giá trị cực đại tạm thời (max) là phần tử đầu tiên của dãy – B2: Nếu số kế tiếp lớn hơn max thì gán giá trị max = số đóMÔN: CẤU TRÚC DỮ LIỆU – B3: Lặp lại bước 2 nếu còn phần tử trong dãy – B4: Dừng khi không còn phần tử trong dãy, số max lúc này là phần tử lớn nhất của dãy6/12/14/XX3GV: NGUYỄN XUÂN VINH Khái niệmMÔN: CẤU TRÚC DỮ LIỆU Dữliệunhập(input) Dữliệuxuất(output)  Dãythaotác6/12/14/XX4GV: NGUYỄN XUÂN VINH Các tính chất cơ bản của thuật toán • Tính xác định (rõ ràng, xác định). • Tính hữu hạn (dừng). • Tính đúng đắn. • Tính tổng quát: phải áp dụng được cho 1 họ các vấn đề • Đầu vàoMÔN: CẤU TRÚC DỮ LIỆU • Đầu ra6/12/14/XX5GV: NGUYỄN XUÂN VINH Độ phức tạp của thuật toánMÔN: CẤU TRÚC DỮ LIỆU Thờigian(sốthaotác) Độphứctạp Dữliệunhập củathuậttoán Khônggian6/12/14/XX6GV: NGUYỄN XUÂN VINH Độ phức tạp của thuật toán • Thời gian mà máy tính khi thực hiện một thuật toán phụ thuộc vào: – Bản thân thuật toán đó. – Máy tính đang thực thi thuật toán. Đánh giá hiệu quả của một thuật toán có thể:MÔN: CẤU TRÚC DỮ LIỆU • – Xét số các phép tính phải thực hiện khi thực hiện thuật toán này.6/12/14/XX7GV: NGUYỄN XUÂN VINH Độ phức tạp của thuật toán • Độ phức tạp về không gian • Độ phức tạp về thời gian • Độ phức tạp về giải thuậtMÔN: CẤU TRÚC DỮ LIỆU6/12/14/XX8GV: NGUYỄN XUÂN VINH Độ phức tạp về không gian • Chiếm tài nguyên của máy – Bộ nhớ – Sử dụng CPU – Băng thôngMÔN: CẤU TRÚC DỮ LIỆU – … • VD: heap sort nếu dùng heap mà không dùng arraytốn bộ nhớ6/12/14/XX9GV: NGUYỄN XUÂN VINH Độ phức tạp về thời gian • Tính hiệu quả của thuật toán được tính bằng phương pháp thực nghiệm thông qua các bộ dữ liệu thử – Phụ thuộc vào ngôn ngữ lập trình – Trình độ, kỹ năng của người viết Phần cứng máy tính dùng để thử nghiệmMÔN: CẤU TRÚC DỮ LIỆU – – Sự phức tạp của việc xây dựng một bộ dữ liệu thử6/12/14/XX10GV: NGUYỄN XUÂN VINH Độ phức tạp về giải thuật • Mang tính hình thức • Phép đo độc lập với máy tính, ngôn ngữ lập trình, người lập trình hay những tiểu tiết: tăng giảm, chỉ số vòng lặp, sự khởi gán,… • Thời gian thực thi của giải thuật sẽ tăng theo kích thước dữ ...