常見的查找演算法

㈠ 幾種查找演算法的比較

文章摘要: 查找是在大量的信息中尋找一個特定的信息元素，在計算機應用中，查找是常用的基本運算，文中介紹四種查找演算法，分別是順序查找、二分查找、二叉排序樹查找和哈希查找。並用JAVA語言編寫了相應程序代碼，比較了查找同一個數據的時間復雜度和空間復雜度。

㈡ 數據結構：重要的查找演算法有哪些

折半查找也就是二分查找，它必須滿足排序關系。
查找也可以用二叉查找樹，一般復雜度為O(logn),最壞為O(n)。
也可用平衡樹進行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。

比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)

堆排序比較有意思，值得研究一下，理解了後，很有用～，也很重要。

㈢ 常見的數據檢索演算法有哪些資料庫都採用什麼樣的檢索方式如何提高檢索的效率

信息檢索方法包括：普通法、追溯法和分段法。1、普通法是利用書目、文摘、索引等檢索工具進行文獻資料查找的方法。運用這種方法的關鍵在於熟悉各種檢索工具的性質、特點和查找過程，從不同角度查找。普通法又可分為順檢法和倒檢法。2、追溯法是利用已有文獻所附的參考文獻不斷追蹤查找的方法，在沒有檢索工具或檢索工具不全時，此法可獲得針對性很強的資料，查准率較高，查全率較差。3、分段法是追溯法和普通法的綜合，它將兩種方法分期、分段交替使用，直至查到所需資料為止。(3)常見的查找演算法擴展閱讀檢索原因信息檢索是獲取知識的捷徑美國普林斯頓大學物理系一個年輕大學生名叫約瀚·菲利普，在圖書館里借閱有關公開資料，僅用四個月時間，就畫出一張製造原子彈的設計圖。他設計的原子彈，體積小(棒球大小)、重量輕(7.5公斤)、威力大(相當廣島原子彈3/4的威力)，造價低(當時僅需兩千美元)，致使一些國家（法國、巴基斯坦等）紛紛致函美國大使館，爭相購買他的設計拷貝。二十世紀七十年代，美國核專家泰勒收到一份題為《製造核彈的方法》的報告，他被報告精湛的技術設計所吸引，驚嘆地說：「至今我看到的報告中，它是最詳細、最全面的一份。」

㈣ 幾種常見的查找演算法之比較

二分法平均查找效率是O(logn)，但是需要數組是排序的。如果沒有排過序，就只好先用O（nlogn)的預處理為它排個序了。而且它的插入比較困難，經常需要移動整個數組，所以動態的情況下比較慢。

哈希查找理想的插入和查找效率是O(1)，但條件是需要找到一個良好的散列函數，使得分配較為平均。另外，哈希表需要較大的空間，至少要比O(n)大幾倍，否則產生沖突的概率很高。

二叉排序樹查找也是O(logn)的，關鍵是插入值時需要做一些處理使得它較為平衡（否則容易出現輕重的不平衡，查找效率最壞會降到O(n)），而且寫起來稍微麻煩一些，具體的演算法你可以隨便找一本介紹數據結構的書看看。當然，如果你用的是c語言，直接利用它的庫類型map、multimap就可以了,它是用紅黑樹實現的，理論上插入、查找時間都是O(logn)，很方便，不過一般會比自己實現的二叉平衡樹稍微慢一些。

㈤ 查找演算法有哪些

查找演算法常用的有，順序查找，二分查找，哈希表查找，等等。

㈥ 查找演算法有哪兩種類型

二分查找又稱折半查找，它是一種效率較高的查找方法。
分塊查找又稱索引順序查找，它是順序查找的一種改進方法。
方法描述：將n個數據元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……。

㈦ 查找的計算機演算法

⒈順序查找的思想是：
將查找值順序逐個與結點值進行比較，相等即為查找成功，否則查找失敗.
程序如下：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
b:boolean;
place:integer;
procere search(r:arr;m,x:integer; var found:boolean;var p:integer);
begin
p:=1;found:=false;
while(p<=m) and not found do
if r[p]=x then found:=true else p:=p+1;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
search(a,n,x1,b,place);
if b then begin writeln('yes');writeln('Place of',x1:5,'is:',place); end
else writeln('no');
end. ⒈二分查找的基本思想：首先將結點按關鍵字排序，其次將查找值與中間位置的值比較，相等，查找成功；不等，則中間數據大於或小於查找值，無論怎樣查找將在一半的數據中查找。
⒉例：輸入序列數據查找指定值.
程序：
program sxcz;
const n=7;
type
arr=array[1..n] of integer;
var x1,i:integer;
a:arr;
place:integer;
procere paixv(var r:arr;m:integer);
var k,j,i,t:integer;
begin
k:=m;
while k>0 do
begin
j:=k-1;k:=0;
for i:=1 to j do
if r[i]>r[i+1] then
begin t:=r[i];a[i]:=r[i+1];r[i+1]:=t;k:=i;end;
end;
end;
procere search(r:arr;m,x:integer; var p:integer);
var low,high,mid:integer;
begin
p:=0;low:=1;high:=m;
while low<=high do
begin
mid:=(low+high) div 2;
if x>r[mid] then low:=mid+1 else
if x<r[mid] then high:=mid-1 else
begin p:=mid;exit;end;
end;
end;
begin
write('Enter array:');
for i:=1 to n do read(a[i]);
writeln;
write('Enter search data:');
read(x1）；
paixv(a,n);
search(a,n,x1,place);
if place<>0 then writeln('yes') else writeln('no');
end. 因為二叉排序樹的左子樹若不為空則左子樹的所有結點的值均小於它的根結點的值，而右子樹若不為空，則右子樹的所有結點的值均不小大於它的根結點的值，根據這個性質查找演算法如下：
program pxtree;
const
a:array[1..8] of integer=（10,18,3,8,12,2,7,3）；
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i,x:integer;
procere maketr(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then maketr(d,right) else maketr(d,left);
end;
function searchtr(x:integer;p:point):boolean;
begin
if p=nil then searchtr:=false
else if x=p^.w then searchtr:=true
else if x<p^.w then searchtr:=searchtr(x,p^.left)
else searchtr:=searchtr(x,p^.right);
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do maketr(a[i],first);
write('want find data x:');read(x);
if searchtr(x,first) then writeln('yes') else writeln('No');
end. 以上講的查找方法基於比較的，查找效率依賴比較次數，其實理想的查找希望不經比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，這樣查找k時，只要根據這個對應關系f找到給定值k的像f(k）。這種對應關系f叫哈希（hash）函數。按這種思想建立的表叫哈希表（也叫散列表）。哈希表存取方便但存儲時容易沖突（collision）：即不同的關鍵字可以對應同一哈希地址。如何確定哈希函數和解決沖突是關鍵。
⒈哈希函數的構造方法
直接定址法：H(k)=k 或H(k)=a*k+b（線形函數）
如：人口數字統計表 地址 1 2 3 ... 100 年齡 1 2 3 ... 100 人數 67 3533 244 ... 4 數字分析法：取關鍵字的若干數位組成哈希地址
如：關鍵字如下：若哈希表長為100則可取中間兩位10進制數作為哈希地址。 81346532 81372242 81387422 81301367 81322817 81338967 81354157 81368537 平方取中法：關鍵字平方後取中間幾位數組成哈希地址
折疊法：將關鍵數字分割成位數相同的幾部分（最後一部分的位數可以不同）然後取幾部分的疊加和（捨去進位）作為哈希地址。
除留余數法：取關鍵字被某個不大於表長m的數p除後所得的余數為哈希地址。
H(k)=k mod p p<=m
隨機數法：H(k)=rondom(k）。
⒉處理沖突的方法
假設地址集為0..n-1，由關鍵字得到的哈希地址為j(0<=j<=n-1）的位置已存有記錄，處理沖突就是為該關鍵字的記錄找到另一個空的哈希地址。在處理中可能得到一個地址序列Hi i=1，2，...k
0<=Hi<=n-1），即在處理沖突時若得到的另一個哈希地址H1仍發生沖突，再求下一地址H2，若仍沖突，再求H3...。怎樣得到Hi呢？
開放定址法：Hi=(H(k)+di) mod m （H(k）為哈希函數；m為哈希表長；di為增量序列）
當di=1，2，3，... m-1 時叫線性探測再散列。
當di=1，-1，2，-2，3，-3，...,k,-k時叫二次探測再散列。
當di=random（m）時叫偽隨機探測序列。
例：長度為11的哈希表關鍵字分別為17，60，29，哈希函數為H(k)=k mod 11，第四個記錄的關鍵字為38，分別按上述方法添入哈希表的地址為8，4，3（隨機數=9）。
再哈希法：Hi=RHi(key) i=1,2,...,k，其中RHi均為不同的哈希函數。
鏈地址法：這種方法很象基數排序，相同的地址的關鍵字值均鏈入對應的鏈表中。
建立公益區法：另設一個溢出表，不管得到的哈希地址如何，一旦發生沖突，都填入溢出表。
⒊哈希表的查找
例：如下一組關鍵字按哈希函數H(k)=k mod 13和線性探測處理沖突所得的哈希表a[0..15]: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 當給定值k=84，則首先和a[6]比在依次和a[7],a[8]比結果a[8]=84查找成功。
當給定值k=38，則首先和a[12]比，再和a[13]比，由於a[13]沒有，查找不成功，表中不存在關鍵字等於38的記錄。 查找第k小元素即在n個元素中（未排序）找到第k小的元素。方法同快速排序，採用遞歸方式。
程序如下：
program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
b:arr;
i,k:integer;
function p(s,t:integer):integer;
var i,j,t1,x:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
p:=i;
end;
function find(s,t,k:integer):integer;
var p1,q:integer;
begin
if s=t then find:=b[s] else
begin
p1:=p(s,t);
q:=p1-s+1;
if k<=q then find:=find(s,p1,k) else find:=find(p1+1,t,k-q);
end;
end;
begin
write('input data:');
for i:=1 to n do read(b[i]);readln;
write('input k:');read(k);
write('output data:');
writeln('kthsmall:=',find（1,n,k));
end.

㈧ 【數據結構】幾種重要的查找演算法。

恩你是要問什麼?

順序查找就是按順序查找,復雜度O(n)

二分查找的前提是數據是有序的 一次復雜度O(logn)
例如在數組 A: 1 3 5 7 8 10 12 中
如果要找 10
我們先看中間的數是 7, 10比7大,那麼繼續在右側二分尋找,這是一個遞歸的過程.
偽代碼:
bool find(int L,int R,int What_You_Want) {
if (L > R) return false;
int mid = (L + R) / 2
if (A[mid] == What_You_Want) return true;
else if (A[mid] > What_You_Want) return find(L,mid - 1,What_You_Want);
else return find(mid + 1, R, What_You_Want);
}

二叉搜索樹的原理與二分查找相同

㈨ 數據結構有哪些基本演算法

數據結構是一門研究非數值計算的程序設計問題中的操作對象，以及它們之間的關系和操作等相關問題的學科。

可以理解為：程序設計 = 數據結構 + 演算法

數據結構演算法具有五個基本特徵：輸入、輸出、有窮性、確定性和可行性。

1、輸入：一個演算法具有零個或者多個輸出。以刻畫運算對象的初始情況，所謂0個輸入是指演算法本身定出了初始條件。後面一句話翻譯過來就是，如果一個演算法本身給出了初始條件，那麼可以沒有輸出。比如，列印一句話：NSLog(@"你最牛逼！");

2、輸出：演算法至少有一個輸出。也就是說，演算法一定要有輸出。輸出的形式可以是列印，也可以使返回一個值或者多個值等。也可以是顯示某些提示。

3、有窮性：演算法的執行步驟是有限的，演算法的執行時間也是有限的。

4、確定性：演算法的每個步驟都有確定的含義，不會出現二義性。

5、可行性：演算法是可用的，也就是能夠解決當前問題。

數據結果的基本演算法有：

1、圖搜索（廣度優先、深度優先）深度優先特別重要

2、排序

3、動態規劃

4、匹配演算法和網路流演算法

5、正則表達式和字元串匹配

6、三路劃分-快速排序

7、合並排序（更具擴展性，復雜度類似快速排序）

8、DF/BF 搜索 （要知道使用場景）

9、Prim / Kruskal （最小生成樹）

10、Dijkstra （最短路徑演算法）

11、選擇演算法