zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM

Chia sẻ: No Comment | Ngày: | Loại File: PPT | Số trang:101

Báo xấu

193
lượt xem 42
download

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

Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần lượt từng phần tử của danh sách với giá trị X cần tìm. Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán dừng lại (thành công). Giải thuật tìm kiếm tuần tự, nhị phân trên danh sách liên kết.

Chủ đề:

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

Lưu

Nội dung Text: PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM

1 P HÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM
Nội dung 2 Giải thuật tìm kiếm tuần tự, nhị phân trên danh  sách liên kết Phân tích các thao tác trên cây tìm kiếm nhị  phân Phân tích các kỹ thuật băm  Phân tích một vài giải thuật so trùng chuỗi 
2. Tìm tuyến tính (Linear Seach) 3 Ý tưởng: Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần  lượt từng phần tử của danh sách với giá trị X cần tìm Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán  dừng lại (thành công) Nếu đến cuối danh sách mà không có phần tử nào bằng X,  thuật toán dừng lại (không thành công)
Tìm tuyến tính (Linear Seach) 4 5 Vị trí = 2 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Tìm thành công Số lần so sánh: 3
2. Tìm tuyến tính (Linear Seach) 5 9 Khóa tìm 0 1 2 3 4 5 6 7 7 13 5 21 6 2 8 15 Không tìm thấy Số lần so sánh: 8
Tìm tuyến tính (Linear Seach) 6 int LSearch(int list[], int n, int key) int LinearSearch(int a[], int { N, int key) { int i=0; int find= 1; while ((i
Tìm tuyến tính (Linear Seach) 7 int LinearSearch(int a[],int N,int key) //Dùng pp lính canh  { int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]  a[N] =key; // thêm phần tử thứ N+1  while (a[i]!= ) i+ ; x +  if (i= N) =  return -1; // tìm hết mảng nhưng không có x  else  return i; // tìm thấy x tại vị trí i  }  Giảm bớt một phép so sánh trong vòng lặp
2. Tìm tuyến tính (Linear Seach) 8 Phân tích, đánh giá thuật toán  Số lần so Trường hợp Giải thích sánh Tốt nhất Phần tử đầu tiên có giá trị x 1 Xấu nhất Phần tử cuối cùng có giá trị x n+1 Giả sử xác suất các phần tử trong Trung bình (n+1)/2 mảng nhận giá trị x là như nhau. Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán  cấp n: T(n) = O(n) Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các  phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
Tìm nhị phân (Binary Seach) 9 Điều kiện:  Danh sách phải được sắp xếp trước  Ý tưởng:  So sánh giá trị muốn tìm X với phần tử nằm ở vị trí giữa  của danh sách: Nếu bằng, tìm kiếm dừng lại (thành công)  Nếu X lớn hơn thì tiếp tục tìm kiếm ở phần danh sách bên phải  phần tử giữa Nếu X nhỏ hơn thì tiếp tục tìm kiếm ở phần danh sách bên trái  phần tử giữa
Tìm nhị phân (Binary Seach) 10 Vi trí = 3 10 Khóa cần tìm lớn hơn Khóa cần tìm nhỏ hơn Khóa tìm Khóa cần tìm bằng 0 1 2 3 4 5 6 7 8 9 2 5 8 10 12 13 15 18 21 24 left mid right Tìm thấy Số lần so sánh: 4
Tìm nhị phân (Binary Seach) 11 Không đệ quy void BSearch (int list[], int n, int key) { int left, right, mid, flag = 0; left = 0; right = n1; while (left
Tìm nhị phân (Binary Seach) 12 Đệ quy int BSearch_Recursion (int list[], int key, int left, int right) { if (left
Tìm nhị phân (Binary Seach) 13 Phân tích, đánh giá thuật toán:  Trường hợp Số lần so sánh Giải thích Tốt nhất Phần tử giữa của mảng có giá trị x 1 log 2 n Xấu nhất Không có x trong mảng Giả sử xác suất các phần tử trong log 2 (n/2) Trung bình mảng nhận giá trị x là như nhau Vậy giải thuật tìm nhị phân có độ phức tạp tính toán cấp  n: T(n) = O(log2n)
Tìm nhị phân (Binary Seach) 14 Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử  mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với  giải thuật tìm tuyến tính do Tnhị phân (n) = O(log 2 n) < Ttuyến tính (n) = O(n). Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét  đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại .
Tìm nhị phân (Binary Seach)_BT 15 1. Xét mảng các số nguyên có nội dung nh ư sau : -9 -9 -5 -2 0 3 7 7 10 15 a. Tính số lần so sánh để tìm ra phần tử X = -9 bằng phương pháp:  Tìm tuyến tính  Tìm nhị phân  Nhận xét và so sánh 2 phương pháp tìm nêu trên trong trường hợp này và trong trường hợp tổng quát. b. Trong trường hợp tìm nhị phân, phần tử nào sẽ được tìm thấy (thứ 1 hay 2) 2. Xây dựng thuật toán tìm phần tử nhỏ nhất (lớn nhất) trong một mảng các số nguyên.
Tìm nhị phân (Binary Seach)_BT 16 Bài tập THỰC HÀNH : 1. Cài đặt các thuật toán tìm kiếm đã trình bày. Th ể hiện trực quan các thao tác của thuật toán. Tính th ời gian thực hiện của mỗi thuật toán. 2. Hãy viết hàm tìm tất cả các số nguyên tố nằm trong mảng một chiều a có n phần tử. 3. Hãy viết hàm tìm dãy con tăng dài nhất của mảng m ột chiều a có n phần tử (dãy con là một dãy liên tiếp các phần của a). 4. Cài đặt thuật toán tìm phần tử trung vị (median) của một dãy số.
Tìm kiếm trên danh sách liên kết 17 Tìm kiếm một phần tử có khóa x  Node* Search (List l, int x) • Tìm kiếm mất tối đa { O(n) nếu danh sách Node* p = l.pHead; có n phần tử while (p!=NULL) { • Trường hợp tốt nhất if (p->data==x) là O(1) return p; p=p->pNext; } return NULL; }
Binary Search Tree Định nghĩa 18 Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân  trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải Nhờ ràng buộc về khóa trên CNPTK, việc tìm  kiếm trở nên có định hướng Nếu số nút trên cây là N thì chi phí tìm kiếm trung  bình chỉ khoảng log2N Trong thực tế, khi xét đến cây nhị phân chủ yếu  người ta xét CNPTK
Binary Search Tree – Vi dụ ́ 19 44 18 88 59 108 13 37 15 23 40 55 71
Binary Search Tree – Khai báo 20 Khai bao câu truc cây nhị phân tìm kiếm: ́ ́ ́  struct TNode { DataType data; TNode *pLeft, *pRight; }; typedef TNode* Tree; Để quản lý cây nhị phân tìm kiếm chỉ cần quản lý  địa chỉ nút gốc: Tree root;

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.