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

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.
Nội dung trích xuất từ tài liệu:
PHÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM 1P HÂN TÍCH CÁC GIẢI THUẬT TÌM KIẾM Nộidung2 Giảithuậttìmkiếmtuầntự,nhịphântrêndanh  sáchliênkết Phântíchcácthaotáctrêncâytìmkiếmnhị  phân Phântíchcáckỹthuậtbăm  Phântíchmộtvàigiảithuậtsotrùngchuỗi  2.Tìmtuyếntính(LinearSeach)3 Ýtưởng: Bắtđầutừphầntửđầutiêncủadanhsách,sosánhlần lượttừngphầntửcủadanhsáchvớigiátrịXcầntìm NếucóphầntửbằngXthìtrảvềvịtrítìmthấy,thuậttoán dừnglại(thànhcông) NếuđếncuốidanhsáchmàkhôngcóphầntửnàobằngX, thuậttoándừnglại(khôngthànhcông) Tìmtuyếntính(LinearSeach)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ìmtuyếntính(LinearSeach)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ìmtuyếntính(LinearSeach) 6intLSearch(intlist[],intn,intkey) int LinearSearch(int a[], int{ N, int key) { int i=0; intfind=1; while ((i Tìmtuyếntính(LinearSeach)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ìmtuyếntính(LinearSeach)8 Phântích,đánhgiáthuậttoá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ậygiảithuậttìmtuyếntínhcóđộphứctạptínhtoán  cấpn: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ìmnhịphân(BinarySeach)9 Điềukiện:  Danhsáchphảiđượcsắpxếptrước  Ýtưởng:  SosánhgiátrịmuốntìmXvớiphầntửnằmởvịtrígiữa  củadanhsách: Nếubằng,tìmkiếmdừnglại(thànhcông)  NếuXlớnhơnthìtiếptụctìmkiếmởphầndanhsáchbênphải  phầntửgiữa NếuXnhỏhơnthìtiếptụctìmkiếmởphầndanhsáchbêntrái  phầntửgiữa Tìmnhịphân(BinarySeach)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ìmnhịphân(BinarySeach)11 Khôngđệquy voidBSearch(intlist[],intn,intkey) { intleft,right,mid,flag=0; left=0;right=n1; while(left Tìmnhịphân(BinarySeach)12 Đệquy intBSearch_Recursion(intlist[],intkey,intleft,intright) { if(left Tìmnhịphân(BinarySeach)13 Phântích,đánhgiáthuậttoá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ậygiảithuậttìmnhịphâncóđộphứctạptínhtoáncấp  n:T(n)=O(log2n) Tìmnhịphân(BinarySeach)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é ...