Bài giảng 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

Chia sẻ: You You | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

83
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 1 giới thiệu tổng quan về cấu trúc dữ liệu và thuật toán. Chương này giúp người học hiểu rõ một số vấn đề như: Khái niệu cấu trúc dữ liệu, thuật toán, sự liên hệ giữa cấu trúc dữ liệu và thuật toán; phân tích thời gian thực hiện giải thuật, phân tích độ phức tạp tính toán của giải thuật, xác định độ phức tạp tính toán.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng 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

Chươ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 1
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 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… 2 2 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
1.1.2 Giải thuật 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, … 3 3 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
1.1.3 Sự liên hệ giữa cấu trúc dữ liệu và giải thuật Cấu trúc dữ liệu + Giải thuật = Chương trình 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. 4 4 Written by: Dương Thành Phết Khoa CNTT Trường Cð CNTT TP.HCM
1.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 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.. 5 5 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
1.2.2 ðánh giá ñộ phức tạp của thuật toán ðá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 6 6 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
1.2.3 Phân tích thuật toán 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. Ký hiệu ô lớn Tên gọi thông thường O(1) Hằng O(log2n) logarit O(n) Tuyến tính O(nlog2n) nlog2n O(n2) Bình phương O(n3) Lập phương O(2n) Mũ 7 7 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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. } 8 8 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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) 9 9 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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). 10 10 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM