Bài giảng Cấu trúc dữ liệu 1 - Nguyễn Thái Dư

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

Thêm vào BST

Báo xấu

82
lượt xem 3
download

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

Bài giảng Cấu trúc dữ liệu 1 gồm có 4 chương. Nội dung cụ thể của các chương như sau: Chương 1 - Tổng quan về giải thuật và cấu trúc dữ liệu, chương 2 - Tìm kiếm và sắp xếp, chương 3 - Cấu trúc dữ liệu động, chương 4 - Cấu trúc cây. Mời các bạn cùng tham khảo.

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 1 - Nguyễn Thái Dư

TRƯỜ TRƯỜNG ĐẠ ĐẠI HỌ HỌC AN GIANG GiỚI THIỆU KHOA KỸ KỸ THUẬ THUẬT- CÔNG NGHỆ NGHỆ - MÔI TRƯỜ TRƯỜNG Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu Chương 2: Tìm kiếm và sắp xếp Chương 3: Cấu trúc dữ liệu động CẤU TRÚC DỮ LIỆU 1 Chương 4: Cấu trúc cây Giảng viên phụ trách: NGUYỄN THÁI DƯ Bộ môn Tin học email: ntdu@agu.edu.vn Nguyễn Thái Dư - AGU 1 1 Nguyễn Thái Dư - AGU 2 MỤC TIÊU Phương pháp học tập Cần biết: GV: Trình bày ngắn gọn Ngôn ngữ: C, Java SV: Đọc tài liệu có liên quan và tự giác làm các bài tập Mục tiêu: trong tài liệu và sách tham khảo. Có hiểu biết tốt về CTDL và GT GV-SV: Giải đáp thắc mắc - Trao đổi Hiểu và cài đặt được các kiểu dữ liệu trừu tượng cơ bản Nắm được các giải thuật về sắp xếp và tìm kiếm Nắm được một số phương pháp thiết kế giải thuật Rèn luyện cách phân tích một bài toán, Tìm ra giải thuật Thể hiện cách phân tích qua NNLT cụ thể (C, Java) Nguyễn Thái Dư - AGU 3 Nguyễn Thái Dư - AGU 4
Phân bố tiết của môn học Tài liệu tham khảo Tổng cộng: 60 tiết Nhập môn Cấu trúc dữ liệu và thuật toán – Hoàng Kiếm Lý thuyết: 30 tiết (chủ biên), Trần Hạnh Nhi, Dương Anh Đức, 2003. Thực hành: 30 tiết Cấu trúc dữ liệu và giải thuật, Đỗ Xuân Lôi, , NXB Khoa học và Kỹ thuật, 1995. Cấu trúc dữ liệu, Nguyễn Văn Linh (chủ biên), ĐH Cần thơ, 2003. Giải thuật, Nguyễn Văn Linh (chủ biên), ĐH Cần thơ, 2003. Data Structures and Algorithm Analysis in C, Mark Allen Weiss, 1992. Algorithms In C, Sedgewick, 1990. Nguyễn Thái Dư - AGU 5 Nguyễn Thái Dư - AGU 6 Tài liệu tham khảo Introduction to Algorithms 2nd, Thomas H. Cormen, 2001. Thắc Sedgewick Robert, Cẩm nang thuật toán, tập 1 và 2, bản dịch của Hoàng Hồng, NXB Khoa học và Kỹ thuật, 2001. Wirth Niklaus, Cấu trúc dữ liệu + Giải thuật = Chương trình, bản dịch của Nguyễn Quốc Cường, Nhà xuất bản Giáo dục, 1993. mắc Nguyễn Thái Dư - AGU 7 Nguyễn Thái Dư - AGU 8
TRƯỜ TRƯỜNG ĐẠ ĐẠI HỌ HỌC AN GIANG Chương 1. TỔNG QUAN CẤU TRÚC DỮ LIỆU KHOA KỸ KỸ THUẬ THUẬT- CÔNG NGHỆ NGHỆ - MÔI TRƯỜ TRƯỜNG Cấu trúc dữ liệu (Data Structures) Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) Giải thuật (Algorithms) Tính tóan độ phức tạp của giải thuật (Computational CẤU TRÚC DỮ LIỆU 1 complexity of algrorithms) Phân tích giải thuật (Algorithm Analysis) Giảng viên phụ trách: NGUYỄN THÁI DƯ Bộ môn Tin học email: ntdu@agu.edu.vn Nguyễn Thái Dư - AGU 1 1 Nguyễn Thái Dư - AGU 2 Cấu trúc dữ liệu (Data Structures) Kiểu dữ liệu trừu tượng (ADT) Cấu trúc dữ liệu dùng để tổ chức dữ liệu Một kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) Thường có nhiều hơn một thành phần là tập hợp các đối tượng và được xác định hoàn toàn Có các thao tác hợp lý trên dữ liệu bởi các phép toán có thể biểu diễn trên các đối tượng đó. Dữ liệu có thể được kết nối với nhau (ví dụ: array) như là một tập hợp. ADT là một mô hình toán của cấu trúc dữ liệu xác định kiểu dữ liệu được lưu trữ, các thao tác được hỗ trợ trên dữ liệu đó và kiểu của các tham số trong từng thao tác. Nguyễn Thái Dư - AGU 3 Nguyễn Thái Dư - AGU 4
Kiểu dữ liệu trừu tượng (ADT) Kiểu dữ liệu trừu tượng (ADT) Có hai loại ADT Các lớp thao tác của một ADT Đơn/nguyên tử: int, char, … Tạo lập đối tượng mới Có cấu trúc: array, struct,… Biến đổi các đối tượng của ADT Ngoài những ADT do ngôn ngữ lập trình cung cấp, – Mang lại những thay đổi cần thiết cho đối tượng người lập trình có tạo ra các ADT của riêng mình Quan sát Trong C, các ADT do người dùng định nghĩa sẽ thông – Cho biết trạng thái của đối tượng qua kiểu cấu trúc (struct), các thao tác được xây dựng Chuyển đổi kiểu bằng các hàm (functions) – Chuyển kiểu từ kiểu này sang kiểu khác Vào ra dữ liệu – Nhập/xuất giá trị cho đối tượng Nguyễn Thái Dư - AGU 5 Nguyễn Thái Dư - AGU 6 Tại sao cần phải học Cấu trúc dữ liệu và Giải Kiểu dữ liệu trừu tượng (ADT) thuật? Person Giải thuật? Cấu thành bởi: Tại sao lại cần phải học giải thuật? Vai trò của giải – Họ tên thuật? Những vấn đề nào sẽ cần giải quyết bằng giải – Ngày sinh thuật? – Nơi sinh Giải thuật: – Phái Là một khái niệm quan trọng nhất trong tin học. Thuật ngữ này xuất phát từ nhà tóa học Ảrập Abu Ja’far Phép toán: Mohammed ibn Musa al Khowarizmi (khỏang năm – Tạo mới một person (với thông tin đầy đủ) 825) – Hiển thị thông tin về một person Thuật tóan nổi tiếng nhất, có từ thời kỳcổ Hy Lạp là – …. thuật tóan Euclid. Là một phương pháp giải quyết vấn đề thích hợp để Nguyễn Thái Dư - AGU 7 cài đặt như một chương trình máy tính. Nguyễn Thái Dư - AGU 8
Tại sao cần phải học Cấu trúc dữ liệu và Giải Tại sao cần phải học Cấu trúc dữ liệu và Giải thuật? thuật? Algorithm: Cấu trúc dữ liệu? A finite sequence of steps for solving a logical or Được tạo ra để phục vụ cho các giải thuật mathematical problem or performing a task. (The Phải hiểu cấu trúc dữ liệu để hiểu giải thuật ⇒ để giải Microsoft Computer Dictionary, Fifth Edition ) quyết vấn đề A computable set of steps to achieve a desired result. Các giải thuật đơn giản có thể cần đến cấu trúc dữ liệu Informally, an algorithm is any well-defined phức tạp computational procedure that takes some value, or set Các giải thuật phức tạp có thể chỉ dùng các cấu trúc of values, as input and produces some value, or set of dữ liệu đơn giản values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output (Introduction to Algorithms, 2nd, Thomas H. Cormen, Cấu trúc dữ liệu + Giải thuật = Chương trình 2001) Nguyễn Thái Dư - AGU 9 Nguyễn Thái Dư - AGU 10 Tại sao cần phải học Cấu trúc dữ liệu và Giải Kiểu dữ liệu thuật? ĐN kiểu dữ liệu Dùng máy tính để: Các thuộc tính của 1 kiểu dữ liệu Giải quyết các vấn đề về tính toán? Tên kiểu dữ liệu Việc giải quyết vấn đề nhanh hơn? Miền giá trí Khả năng truy xuất nhiều dữ liệu hơn? Kích thước lưu trữ Kỹ thuật vs. Thực thi/Giá Tập các tóan tử, phép tóan tác động trên kiểu dữ liệu Kỹ thuật có thể tăng khả năng giải quyết vấn đề bằng nhân tố hằng. Một số kiểu dữ liệu có cấu trúc cơ bản Thiết kế giải thuật tốt có thể giúp giải quyết vấn đề Kiểu chuỗi ký tự (string), Kiểu mảng (array) tốt hơn nhiều và có thể rẻ hơn. Kiểu mẩu tin (struct) Một siêu máy tính không thể giúp một giải thuật tồi Kiểu tập hợp (union) làm việc tốt hơn Nguyễn Thái Dư - AGU 11 Nguyễn Thái Dư - AGU 12
Một số tính chất chung của các thuật tóan Ví dụ Đầu vào (input): có các giá trị đầu vào xác định. Ví dụ: Mô tả thuật toán tìm phần tử lớn nhất trong một Đầu ra (ouput): từ tập các giá trị đầu vào, thuât toán sẽ tạo các dãy hữu hạn các số nguyên giá trị đầu ra, xem là nghiệm của bài toán. Bước 1: Đặt giá trị cực đại tạm thời bằng số nguyên Tính xác định (definiteness): các bước của thuật toán phải được đầu tiên. xác định một cách chính xác. Bước 2: Nếu số nguyên kế tiếp lớn hơn giá trị cực đại Tính hữu hạn (finiteness): một thuật toán chứa một số hữu hạn tạm thời thì gán giá trị cực đại tạm thời bằng số các bước (có thể rất lớn) với mọi tập đầu vào. nguyên đó. Tính hiệu quả(effectiveness): mỗi bước phải thực hiện chính xác, Bước 3: Lặp lại bước 2 nếu còn số nguyên trong dãy. trong khoảng thời gian hữu hạn. Bước 4: Dừng khi không còn số nguyên trên dãy. Giá Tính tổng quát(general): thuật toán phải áp dụng được cho một trị cực đại tạm thời sẽ là số nguyên lớn nhất trong dãy. họ các vấn đề. Nguyễn Thái Dư - AGU 13 Nguyễn Thái Dư - AGU 14 Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân // Tìm tuyến tính // Tìm nhị phân int linearSearch(int a[], int x, int n) int binarySearch(int a[], int x, int n) { { int left = 0, right = N - 1, middle; do { int i = 0; middle = (left + right) / 2; while (i < n) && (a[i] != x) if (a[middle] == x) i++; return TRUE; return (i == n); else if (x < a[middle]) } right = middle – 1; else left = middle + 1; } while (left
Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Ví dụ so sánh - Tìm tuyến tính và tìm nhị phân Để so sánh hai giải thuật, sử dụng n = 32 n Tuần tự Nhị phân Với tìm kiếm tuần tự, giả sử x không có trong mảng a, giải thuật phải xử lý đầy đủ n lần. 256 256 8 Với tìm kiếm nhị phân, dù x có hay không có trong a thì số lần tìm kiếm tối đa chỉ là log2n = 5. 1024 1024 10 1048576 1048576 20 4.294.967.296 4.294.967.296 32 Nguyễn Thái Dư - AGU 17 Nguyễn Thái Dư - AGU 18 Ví dụ so sánh - Fibonacci Ví dụ so sánh - Fibonacci // Tính Fibonacci(n) // Tính Fibonacci(n) int fib1(int n) int fib2(int n) { if (n
Ví dụ so sánh - Fibonacci Phân tích thuật tóan n n+1 2n/2 fib2() fib1() Độ phức tạp về không gian (space complexity) Độ phức tạp về thời gian (time complexity) 40 41 1,048,576 41 ns 1048 μs Độ phức tạp về giải thuật (complexity of algorithm) 60 61 1.1 × 109 61 ns 1s 80 81 1.1 × 1012 81 ns 18 min 100 101 1.1 × 1015 101 ns 13 days 120 121 1.2 × 1018 121 ns 36 years 160 161 1.2 × 1024 161 ns 3.8 × 107 years 200 201 1.3 × 1030 201 ns 4 × 1013 years Nguyễn Thái Dư - AGU 21 Nguyễn Thái Dư - AGU 22 Độ phức tạp về không gian (space complexity) Độ phức tạp về thời gian (time complexity) Chiếm tài nguyên của máy: Tính hiệu quả của giải thuật được kiểm tra bằng Bộ nhớ phương pháp thực nghiệm, thông qua các bộ dữ liệu Sử dụng CPU thử: Băng thông Phụ thuộc vào ngôn ngữ lập trình. … Trình độ, kỹ năng có được 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ử. Nguyễn Thái Dư - AGU 23 Nguyễn Thái Dư - AGU 24
Độ phức tạp về giải thuật (complexity of Tiêu chuẩn đánh giá một giải thuật là tốt algorithm) Một giải thuật được xem là tốt nếu nó đạt các tiêu Mang tính hình thức. chuẩn sau: Phép đo độc lập với máy tính, ngôn ngữ máy tính, Thực hiện đúng. người lập trình, … hay những “tiểu tiết”: tăng/giảm chỉ Tốn ít bộ nhớ. số vòng lặp, sự khởi tạo, gán, … Thực hiện nhanh. Thời gian thực thi của một giải thuật sẽ tăng theo kích Trong khuôn khổ môn học này, chúng ta chỉ quan tâm thước dữ liệu và thời gian này tỉ lệ với số lượng các đến tiêu chuẩn thực hiện nhanh. thao tác cơ sở. Độ phức tạp của giải thuật là một hàm số trên kích thước dữ liệu. Nguyễn Thái Dư - AGU 25 Nguyễn Thái Dư - AGU 26 Độ phức tạp về giải thuật (complexity of Độ phức tạp giải thuật (Algorithm Complexity) algorithm) Những thao tác cơ sở có thể là: Thời gian thực hiện chương trình (Running Time). - Phép so sánh Đơn vị đo thời gian thực hiện: - Phép chuyển dời – T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào. T(n) ≥ 0 với mọi n ≥ 0. - Phép toán số học, … Thông thường người ta tính thời gian thực hiện xấu Thao tác cơ sở là thao tác mang lại hiệu quả cao nhất. nhất (the worst case): Trong các giải thuật sắp xếp, hai thao tác cơ bản là: so – T(n) là thời gian lớn nhất để thực hiện chương trình sánh và chuyển dời. đối với mọi dữ liệu vào có cùng kích thước n. Nguyễn Thái Dư - AGU 27 Nguyễn Thái Dư - AGU 28
Tỷ suất tăng (growth rate) Khái niệm độ phức tạp của giải thuật T(n) có tỷ suất tăng f(n) nếu tồn tại các hằng số C và Giả sử ta có hai giải thuật P1 và P2 N0 sao cho T(n) ≤ Cf(n) với mọi n ≥ N0. P1: T1(n) = 100n2 (tỷ suất tăng là n2) Ví dụ: P2 : T2(n) = 5n3 (tỷ suất tăng n3). Giả sử T(0) = 1, T(1) = 4, tổng quát T(n) = (n+1)2 Giải thuật nào sẽ thực hiện nhanh hơn? Ðặt N0 = 1 và C = 4 thì ∀n ≥1, Với n < 20 thì P2 sẽ nhanh hơn P1 (T2 20 thì P2 sẽ nhanh hơn P1 (T2
Tính tóan độ phức tạp (Computational Complexity) Tính tóan độ phức tạp (Computational Complexity) Qui tắc nhân: Qui tắc tổng quát để phân tích một chương trình: Nếu T1(n) và T2(n) là thời gian thực hiện của hai đoạn lệnh gán, scanf, printf là O(1) chương trình P1và P2 và T1(n) = O(f(n)), T2(n) = chuỗi tuần tự các lệnh được xác định bằng qui tắc cộng O(g(n)) thì thời gian thực hiện của đoạn hai đoạn => Như vậy thời gian này = thời gian thi hành một lệnh chương trình đó lồng nhau là T(n) = O(f(n).g(n)) nào đó lâu nhất. Thời gian thực hiện cấu trúc IF là thời gian lớn nhất thực hiện lệnh sau THEN hoặc sau ELSE và thời gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1). Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện thân vòng lặp. Nếu thời gian thực hiện thân vòng lặp không đổi thì thời gian thực hiện vòng lặp là tích của số lần lặp với thời gian thực hiện thân vòng lặp. Nguyễn Thái Dư - AGU 33 Nguyễn Thái Dư - AGU 34 Tính tóan độ phức tạp (Computational Complexity) Khái niệm độ phức tạp của giải thuật void BubbleSort(int list[], int n) Giả sử ta có hai giải thuật P1 và P2 với thời gian thực { int i,j,temp; hiện tương ứng là T1(n) = 100n2 (với tỷ suất tăng là n2) (1) for(i=0;i list[j+1]) O(1) của T1 nhỏ hơn tỷ suất tăng của T2. (4) { temp = list[j]; O(1) Như vậy một cách hợp lý là ta xét tỷ suất tăng của hàm thời gian thực hiện chương trình thay vì xét chính bản (5) list[j]= list[j+1]; O(1) thân thời gian thực hiện. (6) list[j+1]= temp; O(1) Cho một hàm T(n), T(n) gọi là có độ phức tạp f(n) nếu } tồn tại các hằng C, N0 sao cho T(n) ≤ Cf(n) với mọi n } ≥ N0 (tức là T(n) có tỷ suất tăng là f(n)) và kí hiệu T(n) là O(f(n)) (đọc là “ô của f(n)”). Nguyễn Thái Dư - AGU 35 Nguyễn Thái Dư - AGU 36
Khái niệm độ phức tạp của giải thuật Ví dụ 1: Thủ tục sắp xếp “nổi bọt” Chú ý: O(C.f(n))=O(f(n)) với C là hằng số. Ðặc biệt void BubbleSort(int a[n]) O(C)=O(1) { int i,j,temp; Các hàm thể hiện độ phức tạp có các dạng thường gặp sau: log2n, n, nlog2n, n2, n3, 2n, n!, nn. /*1*/ for(i= 0; i=i+1;j--) khác gọi là hàm đa thức. /*3*/ if (a[j].key < a[j-1].key) { Một giải thuật mà thời gian thực hiện có độ phức tạp là /*4*/ temp = a[j-1]; một hàm đa thức thì chấp nhận được, còn các giải thuật có độ phức tạp hàm mũ thì phải tìm cách cải tiến /*5*/ a[j-1] = a[j]; giải thuật. /*6*/ a[j] = temp; Trong cách viết, ta thường dùng logn thay thế cho log2n cho gọn. } } Nguyễn Thái Dư - AGU 37 Nguyễn Thái Dư - AGU 38 Tính thời gian thực hiện của thủ tục sắp xếp “nổi bọt” Tính độ phức tạp của hàm tìm kiếm tuần tự int linearSearch(int a[], int x, int n) { /* 1*/ int index = 0; /* 2*/ while (index < n) { /* 3*/ if (a[index] = = x) return 1; /* 4*/ index ++; } /* 5*/ return 0; } Nguyễn Thái Dư - AGU 39 Nguyễn Thái Dư - AGU 40
Độ phức tạp về giải thuật (complexity of Tính độ phức tạp của hàm tìm kiếm tuần tự algorithm) void ExchangeSort(int n, int a[]) { for (i = 0; i < n - 1; i++) for (j = i + 1; j< n; j++) if (a[j] < a[i]) swap(a[i], S[j]); } n(n − 1) T (n) = (n − 1) + (n − 2) + K + 1 = 2 Nguyễn Thái Dư - AGU 41 Nguyễn Thái Dư - AGU 42 Độ phức tạp về giải thuật (complexity of Ðộ phức tạp của chương trình algorithm) có gọi chương trình con không đệ qui void MatrixMult(int n, A[][], B[][], C[][]) Giả sử ta có một hệ thống các chương trình gọi nhau { theo sơ đồ sau for (i = 0; i < n; i++) for (j = 0; j < n; j++) A B B1 B11 { C[i][j] = 0; for (k = 0; k < n; k++) C[i][j] = C[i][j] + A[i][k] * B[k][j]; } C B2 B12 } T ( n) = n × n × n = n 3 Nguyễn Thái Dư - AGU 43 Nguyễn Thái Dư - AGU 44
Phân tích các chương trình đệ qui Chương trình đệ quy Có thể thấy hình ảnh chương trình đệ quy A như Để giải bài toán kích thước n, phải có ít nhất một sau: trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k
Ví dụ về phương trì trình đệ đệ quy củ của chương trì trình đệ đệ quy tí tính n! Giải thuật MergeSort List MergeSort (List L; int n){ List L1,L2 if (n==1) RETURN(L); else { Chia đôi L thành L1 và L2, với độ dài n/2; RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2))); }; }; Hàm MergeSort nhận một danh sách có độ dài n và trả về một danh sách đã được sắp xếp. Thủ tục Merge nhận hai danh sách đã được sắp L1 và L2 mỗi danh sách có độ dài n/2, trộn chúng lại với nhau để được một danh sách gồm n phần tử có thứ tự. Nguyễn Thái Dư - AGU 49 Nguyễn Thái Dư - AGU 50 Mô hình minh hoạ Mergesort Phương trình đệ quy của giải thuật MergeSort Sắp xếp danh sách L gồm 8 phần tử 7, 4, 8, 9, 3, 1, 6, Gọi T(n) là thời gian thực hiện MergeSort một danh 2 sách n phần tử 7 4 8 9 3 1 6 2 Thì T(n/2) là thời gian thực hiện MergeSort một danh 7 4 8 9 3 1 6 2 sách n/2 phần tử. Khi L có độ dài 1 (n = 1) thì chương trình chỉ làm một 7 4 8 9 3 1 6 2 việc duy nhất là return(L), việc này tốn O(1) = C1 thời gian. 7 4 8 9 3 1 6 2 Trong trường hợp n > 1, chương trình phải thực hiện 4 7 8 9 1 3 2 6 gọi đệ quy MergeSort hai lần cho L1 và L2 với độ dài n/2 do đó thời gian để gọi hai lần đệ quy này là 2T(n/2). 4 7 8 9 1 2 3 6 1 2 3 4 6 7 8 9 Nguyễn Thái Dư - AGU 51 Nguyễn Thái Dư - AGU 52
Phương trình đệ quy của giải thuật MergeSort Giải phương trình đệ quy Ngoài ra còn phải tốn thời gian cho việc chia danh Có ba phương pháp giải phương trình đệ quy: sách L thành hai nửa bằng nhau và trộn hai danh Phương pháp truy hồi. sách kết quả (Merge). Phương pháp đoán nghiệm. Người ta xác định được thời gian để chia danh sách Lời giải tổng quát của một lớp các phương trình và Merge là O(n) = C2n . đệ quy. Vậy ta có phương trình đệ quy? Nguyễn Thái Dư - AGU 53 Nguyễn Thái Dư - AGU 54 Các cấ cấp thờ thời gian thự thực hiệ hiện thuậ thuật tó tóan Các mức đánh giá (Typical growh rates) Trường hợp tốt nhất (best case complexity) Ký hiệu ô lớn (Big-O Notation) Tên gọi thông thường (name) - Function Trường hợp trung bình (average case complexity) O(1) hay C Hằng (constant) Trường hợp xấu nhất (worst case complexity) O(logn) Logarit (logarithmic) O(log2n) Log-squared O(n) Tuyến tính (Linear) O(nlogn) n logarit O(n2) Bình phương (Quadratic) O(n3) Lập phương (Cubic) O(2n) Mũ (exponential) Nguyễn Thái Dư - AGU 55 Nguyễn Thái Dư - AGU 56
Qui tắc tính thời gian Qui tắc tính thời gian Luật 1: Cho các vòng lặp Thời gian : O(n2) Là thời gian lâu nhất của các lệnh trong vòng lặp for( i=0; i
TRƯỜ TRƯỜNG ĐẠ ĐẠI HỌ HỌC AN GIANG Chương 2. TÌM KIẾM VÀ SẮP XẾP KHOA KỸ KỸ THUẬ THUẬT- CÔNG NGHỆ NGHỆ - MÔI TRƯỜ TRƯỜNG Nhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTT Các giải thuật tìm kiếm nội Tìm kiếm tuyến tính Tìm kiếm nhị phân CẤU TRÚC DỮ LIỆU 1 Các giải thuật sắp xếp nội Giảng viên phụ trách: NGUYỄN THÁI DƯ Bộ môn Tin học email: ntdu@agu.edu.vn Nguyễn Thái Dư - AGU 1 1 Nguyễn Thái Dư - AGU 2 Nhu cầu tìm kiếm và sắp xếp dữ liệu trong HTTT Mô tả bài toán Nhu cầu? Cho mảng A[1..n] các đối tượng, có các khóa key Các giải thuật tìm kiếm nội (Searching Techniques) Chúng ta cần tìm trong mảng có phần tử nào có giá trị Tìm kiếm tuyến tính (Sequential Search) bằng x hay không? Tìm kiếm nhị phân (Linear Search) Lưu ý: Khi cài đặt bằng ngôn ngữ C, do chỉ số mảng trong C bắt đầu từ 0 lên các giá trị chỉ số có thể chênh lệnh so với thuật tóan Để đơn giản: Dùng mảng các số nguyên làm cơ sở để cài đặt thuật tóan. Nguyễn Thái Dư - AGU 3 Nguyễn Thái Dư - AGU 4
Tìm kiếm tuyến tính (Sequential Search) Tìm kiếm tuyến tính Ý tưởng: Giải thuật Đây là giải thuật tìm kiếm cổ điển Bước 1: i=1; //Bắt đầu từ phần từ đầu tiên Thuật tóan tiến hành so sánh x với lần lượt với phần Bước 2: So sánh a[i].key với x có 2 khả năng tử thứ nhất, thứ hai,.. của mảng a cho đến khi gặp • a[i].key = x: Tìm thấy, Dừng; được phần tủ có khóa cần tìm. • a[i].key # x: Sang bước 3; Bước 3: • i=i +1; //Xét tiếp phần tử kế tiếp trong mảng • Nếu i>n: hết mảng, không tìm thấy. Dừng • Ngược lại: lặp lại bước 2 Nguyễn Thái Dư - AGU 5 Nguyễn Thái Dư - AGU 6 Tìm kiếm tuyến tính – ví dụ Tìm kiếm tuyến tính – cài đặ đặt Cách 1 Tìm giá trị x =5, x=46, x=19 void LinearSearch(int a[], int N, int x) { int i, flag = 0; for(i=0;i
Tìm kiếm tuyến tính – cài đặt Tìm kiếm tuyến tính – cài đặt Cách 2 Cách 3 int LinearSearch (int a[], int N, int x) int LinearSearch (int a[], int N, int x) { int i=0; { int i=0; while ((i