Cấu trúc dữ liệu và thuật toán - Chương 1: Tổng quan về cấu trúc dữ liệu và thuật toán

1Chương 1 TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU & THUẬT TOÁN 1.1. Khái niệm về cấu trúc dữ liệu và thuật toán 1.1.1. Cấu trúc dữ liệu 1.1.2. Thuật toán 1.1.3. Sự liên hệ giữa cấu trúc dữ liệu và thuât toán 1.2. Phân tích giải thuật 1.2.1. Phân tích thời gian thực hiện giải thuật 1.2.2. ðộ phức tạp tính toán của giải thuật 1.2.3. Xác ñịnh ñộ phức tạp tính toán 1.3. Bài tập 21.1 Khái niệm về cấu trúc dữ liệu và thuật toán 1.1.1 Cấu trúc dữ liệu 2
Bất kỳ một chương trình máy tính nào cũng cần có dữ liệu ñể xử lý.
Dữ liệu vào (input data), dữ liệu trung gian xử lý hoặc dữ liệu ra (output data).
Do vậy, việc tổ chức ñể lưu trữ dữ liệu cho chương trình có ý nghĩa rất quan trọng, quyết ñịnh rất lớn ñến chất lượng cũng như công sức của người lập trình trong thiết kế, cài ñặt chương trình Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 31.1.2 Giải thuật 3
Giải thuật - Thuật giải - Thuật toán dùng ñể chỉ phương pháp hay cách thức ñể giải quyết vần ñề.
Giải thuật có thể ñược minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ ñồ (flow chart) hoặc bằng mã giả pseudo code).
Trong thực tế, giải thuật thường ñược minh họa bằng mã giả tựa ngôn ngữ lập trình nào ñó như C, Pascal, Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 41.1.3 Sự liên hệ giữa cấu trúc dữ liệu và giải thuật 4 Written by: Dương Thành Phết
Cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện chương trình bằng một ngôn ngữ cụ thể chỉ là vấn ñề thời gian.
Một chương trình máy tính chỉ có thể ñược hoàn thiện khi có ñầy ñủ cả Cấu trúc dữ liệu ñể lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu của bài toán ñặt ra. Cấu trúc dữ liệu + Giải thuật = Chương trình Khoa CNTT Trường Cð CNTT TP.HCM 51.2. Phân tích giải thuật 1.2.1 Các tiêu chuẩn ñánh giá cấu trúc dữ liệu 5
Phải tiết kiệm tài nguyên (bộ nhớ trong),
Phải phản ảnh ñúng thực tế của bài toán,
Phải dễ dàng trong việc thao tác dữ liệu.. Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 61.2.2 ðánh giá ñộ phức tạp của thuật toán 6 ðánh giá ñộ phức tạp của một thuật toán là ước lượng thời gian thực hiện thuận toán T(n) ñể so sánh tương ñối giữa các thuật toán. Thời gian thực hiện một thuật toán còn phụ thuộc rất nhiều ñiều kiện khác như: cấu tạo máy tính, dữ liệu ñưa vào, , ta chỉ xét trên mức ñộ của lượng dữ liệu ñưa vào ñể ước lượng thời gian thực hiện:
Trong trường hợp tốt nhất: Tmin
Trong trường hợp xấu nhất: Tmax Và ước lượng thời gian trung bình Tavg Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 71.2.3 Phân tích thuật toán 7 Bảng các cấp thời gian thực hiện thuật toán ñược sử dụng rộng rãi. Lập phươngO(n3) Tuyến tínhO(n) logaritO(log2n) HằngO(1) nlog2nO(nlog2n) Tên gọi thông thườngKý hiệu ô lớn Bình phươngO(n2) MũO(2n) Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 88 Ví dụ: Tìm trong dãy số a1, a2,..., an một phần tử có giá trị bằng x. Vào: Dãy số nguyên a[N] và khoá cần tìm x Ra: Vị trí phần tử có khoá x hoặc là -1 nếu không tìm thấy. Int Timtuyentinh (int a[] , int N , int x) { int i; i = 0; while((i < N) && (a[i] != x)) i=i+1; if( i == N) return -1 ; // hết mảng không có x else return i ; //a[i] là phần tử có khóa x. } Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 99
Nếu a[0] = x thì lệnh i := i + 1 trong vòng lặp thực hiện 1lần. Do ñó thời gian tính tốt nhất của thuật toán là O(1).
Nếu x không có trong dãy thì lệnh i := i + 1ñược thực hiện n lần. Vì thế thời gian tính xấu nhất là O(n).
Thời gian tính trung bình của thuật toán.  Nếu x ñược tìm thấy ở vị trí thứ i thì lệnh i := i + 1 thực hiện i lần (i = 1, 2, ..., n),  Nếu x không xuất hiện trong dãy thì lệnh i := i + 1 thực hiện n lần. [(1 + 2 + ... + n) + n] /(n + 1) Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net 10 10 Ta có: [(1 + 2 + ... + n) + n] /(n + 1) ≤ (n2 + n)/(n + 1) = n Vậy thời gian tính trung bình của thuật toán là O(n). Khoa CNTT Trường Cð CNTT TP.HCM© Dương Thành Phết-www.thayphet.net