Bài giảng Cấu trúc dữ liệu và giải thuật chương 1: Cấu trúc dữ liệu và phân tích thuật toán

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương 1: CẤU TRÚC DỮ LIỆU VÀ PHÂN TÍCH THUẬT TÓAN I. Quan hệ giữa cấu trúc dữ liệu và thuật toán 1. Biểu diễn dữ liệu Giúp cho người lập trình không mất thời gian ở các kiểu dữ liệu ở mức thấp. Ngôn ngữ lập trình cấp cao cung cấp: dữ liệu trừu tượng đơn giản và có cấu trúc. Tác động Có 2. Quan hệ giữa cấu trúc dữ liệu và thuật toán Kiểu Dữ Liệu Thao tác 3. Các bước để giải một bài toán trên máy tính Xác định bài toán, phân tích, đặc tả và mô hình hoá bài toán Thiết kế dữ liệu Thiết kế và phân tích giải thuật Lập trình và gỡ rối Kiểm tra phần mềm Bảo trì II. Thuật toán và phân tích thuật toán 1. Thuật toán Là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán, hành động để giải quyết một vấn đề 2. Biểu diễn thuật toán Mã giả Sơ đồ khối Ngôn ngữ cấp cao 3. Các vấn đề liên quan đến thuật toán Thiết kế thuật toán: Các giải thuật Tính đúng đắn: Kiểm chứng (vắt cạn, lý thuyết) Phân tích thuật tóan 4. Phân tích thuật toán a. Tính hiệu quả Đơn giản, dễ hiểu, dễ cài đặt Tiết kiệm tài nguyên, chạy nhanh nhất có thể Cái nào quan trọng? b. Đánh giá thời gian thực hiện thuật toán Thực nghiệm Lý thuyết: Thời gian thực hiện thuật toán như một hàm số T(n), với n là cỡ dữ liệu vào, với các trường hợp tốt nhất Ttn(n), trung bình Ttb(n), xấu nhất Txn(n). Ví dụ: n là số phần tử của dãy, số chiều ma trận, số bậc phương trình. T(n) là số phép toán sơ cấp cần phải tiến hành trong thuật toán. Phép toán sơ cấp: các phép toán số học, so sánh, gán, đọc, viết… c. Kí hiệu O lớn và đánh giá thời gian thực hiện bằng O lớn Cho n là số nguyên không âm, T(n) và f(n) là các hàm thực không âm. Ta nói T(n)=O(f(n)) {đọc là: T(n) là ô lớn của f(n)} nếu và chỉ nếu tồn tại các hằng số C, n0 sao cho T(n)=n0 Nếu 1 thuật toán có thời gian chạy T(n)=O(f(n)) ta nói thuật toán có thời gian thực hiện cấp f(n). Ví dụ: T(n)=n2+5n+4=1 Vậy T(n)=O(n2), vậy thời gian thực hiện cấp n2 Thường người ta chọn f(n) là hàm số nhỏ nhất Các hàm số thường dùng: f(n)=1 (hàm hằng) f(n)=n, n2, n3, …(hàm đa thức) f(n)=log(n) (hàm logarit) f(n)=nlogn f(n)=n!, nn (hàm mũ) d. Các qui tắc tính Nếu T1(n)=O(f(n)) và T2(n)=O(g(n)) thì Qui tắc tổng: T1(n)+T2(n)=O(max(f(n),g(n))) Qui tắc nhân: T1(n)*T2(n)=O(f(n)*g(n)) Các ví dụ