Bài giảng Cấu trúc dữ liệu và giải thuật: Các khái niệm cơ bản - Lê Thị Ngọc Hạnh

Chương này giới thiệu một số khái niệm cơ bản trong cấu trúc dữ liệu và giải thuật. Các nội dung chính trong chương gồm: Tổng quan về cấu trúc dữ liệu, tiêu chuẩn đánh giá thuật toán, độ tăng của hàm, độ phức tạp của thuật toán, các phương pháp đánh giá độ phức tạp. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các khái niệm cơ bản - Lê Thị Ngọc Hạnh CÁC KHÁI NIỆM CƠ BẢN GV: LÊ THỊ NGỌC HẠNH 1 8/21/2015 Data Structure & Algorithm NỘI DUNG 1. Tổng quan về cấu trúc dữ liệu 2. Tiêu chuẩn đánh giá thuật toán 3. Độ tăng của hàm 4. Độ phức tạp của thuật toán 5. Các phương pháp đánh giá độ phức tạp 8/21/2015 Data Structure & Algorithm 2 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU Bài toán thực tế Trừu tượng hóa Đơn giản hóa 8/21/2015 Data Structure & Algorithm 3 MÔ HÌNH DỮ LIỆU  Mô hình dữ liệu (data model) là các trừu tượng dùng để mô tả bài toán, thông thường là mô tả cách thức mà dữ liệu (data) được biểu diễn (represented) và truy xuất (accessed) như thế nào. 8/21/2015 Data Structure & Algorithm 4 KIỂU DỮ LIỆU  Kiểu dữ liệu (của biến) là một khái niệm trong lập trình, chỉ tập các giá trị mà biến có thể chấp nhận.  Ví dụ: • Kiểu dữ liệu kiểu số nguyên, • Kiểu dữ liệu kiểu số thực, • Kiểu dữ liệu chuỗi 8/21/2015 Data Structure & Algorithm 5 KIỂU DỮ LIỆU CƠ BẢN  Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị của nó là đơn nhất.  Ví dụ: Trong ngôn ngữ lập trình C chuẩn, kiểu int gọi là kiểu sơ cấp vì kiểu này bao gồm các số nguyên từ -32768 đến 32767 và các phép toán +, -, *, /, %…  Mỗi ngôn ngữ đều có cung cấp sẵn các kiểu dữ liệu cơ bản (basic data type), gọi là kiểu dữ liệu chuẩn.  Ví dụ, trong ngôn ngữ C thì các kiểu sau là kiểu dữ liệu cơ bản: int, char, float… 8/21/2015 Data Structure & Algorithm 6 KIỂU DỮ LIỆU CÓ CẤU TRÚC  Kiểu dữ liệu có cấu trúc (Structured Data Type): là kiểu dữ liệu mà giá trị của nó là sự kết hợp các giá trị khác.  Ví dụ: • Kiểu dữ liệu mô tả lý lịch sinh viên. • Kiểu dữ liệu mô tả các thuộc tính của con người. 8/21/2015 Data Structure & Algorithm 7 CẤU TRÚC DỮ LIỆU  Cấu trúc dữ liệu (CTDL): là các đơn vị cấu trúc của ngôn ngữ lập trình dùng để biểu diễn các mô hình dữ liệu. Ví dụ như mảng (array), tập tin (file), danh sách liên kết (linked list)…  Các cấu trúc dữ liệu được chọn phải có khả năng biểu diễn được tập input và output của bài toán cần giải. Hơn nữa, phải phù hợp với các thao tác của thuật toán và cài đặt được bằng ngôn ngữ lập trình đã được lựa chọn. 8/21/2015 Data Structure & Algorithm 8 CHƯƠNG TRÌNH Cấu trúc dữ Giải Chương liệu thuật trình 8/21/2015 Data Structure & Algorithm 9 TIÊU CHUẨN ĐÁNH GIÁ THUẬT TOÁN  Tốc độ thực thi.  Tính chính xác.  Đơn giản, dễ hiểu, dễ bảo trì.  Mức phổ dụng … 8/21/2015 Data Structure & Algorithm 10 ĐÁNH GIÁ ĐỘ PHỨC TẠP  Độ phức tạp thuật toán được thể hiện qua khối lượng thời gian và không gian để thực hiện thuật toán. • Không gian: yêu cầu bộ nhớ, thiết bị lưu trữ,… • Thời gian: tổng thời gian cần thiết để hoàn thành thuật toán 8/21/2015 Data Structure & Algorithm 11 ĐỘ PHỨC TẠP THỜI GIAN  Được đánh giá dựa vào số lượng các thao tác được sử dụng trong thuật toán trên bộ dữ liệu đầu vào được gọi là độ phức tạp tính toán  Các thao tác được xem xét: • Phép so sánh • Phép gán  Đánh giá bằng cách tính số lượng các phép toán quan trọng theo độ lớn của dữ liệu.  Từ đó, thời gian thực hiện của một thuật toán có thể được đánh giá theo một hàm phụ thuộc vào độ lớn đầu vào. 8/21/2015 Data Structure & Algorithm 12 PHÂN LOẠI ĐỘ PHỨC TẠP  Trường hợp tốt nhất: là thời gian nhỏ nhất cần để thực hiện thuật toán  ký hiệu: T(n)  Trường hợp xấu nhất: là thời gian lớn nhất cần để thực hiện Ký hiệu: t(n)  Trường hợp trung bình: tính cho trường hợp tổng quát. 8/21/2015 Data Structure & Algorithm 13 VÍ DỤ  Bước 1. Gán tổng = 0. Gán i = 0.  Bước 2. • Tăng i thêm 1 đơn vị. • Gán Tổng = Tổng + i  Bước 3. So sánh i với 10 • Nếu i < 10, quay lại bước 2. • Ngược lại, nếu i ≥ 10, dừng thuật toán. Số phép gán của thuật toán là bao nhiêu? Số phép so sánh là bao nhiêu? 8/21/2015 Data Structure & Algorithm 14 KÍ HIỆU O  Thông thường không quan tâm đến con số chính xác thời gian thực hiện của thuật toán. Mà quan tâm đến khi tăng kích cỡ của dữ liệu đầu vào thì thời gian thực hiện tăng như thế nào?  Ví dụ: t(n) = 20n2+5n+1 T(n) = n2+10n+1  Định nghĩa: Cho hai hàm số thực f và g có miền xác định trong tập N. Ta viết: f(n)  O(g(n)) và nói f(n) có cấp cao nhất là g(n) hay f(n) thuộc lớp O(g(n)), khi đó có một hằng số C sao cho: | f(n) |  C. | g(n) | 8/21/2015 Data Structure & Algorithm 15 KÍ HIỆU O Ví dụ: t(n) = 20n2 + 5n+1 và T(n)=n2+10n+1 thì t(n) và T(n) có cấp cao nhất là n2  t(n)  O(n2) và T(n)  O(n2) 8/21/2015 Data Structure & Algorithm 16 ĐỘ TĂNG CỦA TỔ HỢP CÁC HÀM Cho f1(x) là O(g1(x)) và f2(x) là O(g2(x)). Khi đó:  Quy tắc tổng: (f1+f2)(x) là O(max(|g1(x)|, |g2(x)|))  Quy tắc nhân: (f1f2)(x) là O(g1(x)g2(x)) 8/21/2015 Data Structure & Algorithm 17 ĐỘ PHỨC TẠP THUẬT TOÁN 8/21/2015 Data Structure & Algorithm 18 ĐỘ PHỨC TẠP CỐ ĐỊNH CỦA THUẬT TOÁN Thuật toán minh họa:  B1. Đặt giá trị cực đại tạm thời bằng số nguyên đầu tiên trong dãy.  B2. So sánh số nguyên tiếp sau với giá trị cực đại tạm thời. Nếu nó lớn hơn giá trị cực đại tạm thời thì đặt cực đại tạm thời bằng số nguyên đó.  B3. Lặp lại B2 nếu còn các số nguyên trong dãy.  B4. Dừng khi không còn số nguyên nào nữa trong dãy. Cực đại tạm thời chính là số nguyên lớn nhất của dãy. 8/21/2015 Data Structure & A ...