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, | ĐỘ PHỨC TẠP (Complexity) Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] 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 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ố đó 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ãy Dữ liệu nhập (input) Dữ liệu xuất (output) Dãy thao tác Khái niệm 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ào Đầu ra Độ phức tạp của thuật toán Độ . | ĐỘ PHỨC TẠP (Complexity) Nguyễn Xuân Vinh nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] 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 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ố đó 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ãy Dữ liệu nhập (input) Dữ liệu xuất (output) Dãy thao tác Khái niệm 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ào Đầu ra Độ phức tạp của thuật toán Độ phức tạp của thuật toán Thời gian (số thao tác) Không gian Dữ liệu nhập Độ 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ể: 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. Độ 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ật Độ 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ông VD: heap sort nếu dùng heap mà không dùng array tốn bộ nhớ Độ 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ệm Sự phức tạp của việc xây dựng một bộ dữ liệu thử Độ 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, .
