相鄰搜索演算法

❶ 運動估計的搜索演算法

匹配誤差函數，可以用各種優化方法進行最小化，這就需要我們開發出高效的運動搜索演算法，
主要的幾種演算法歸納如下： 為當前幀的一個給定塊確定最優位移矢量的全局搜索演算法方法是：在一個預先定義的搜索區域
內，把它與參考幀中所有的候選塊進行比較，並且尋找具有最小匹配誤差的一個。這兩個塊之間的
位移就是所估計的 MV，這樣做帶來的結果必然導致極大的計算量。
選擇搜索區域一般是關於當前塊對稱的，左邊和右邊各有 Rx 個像素，上邊和下邊各有 Ry個像素。
如果已知在水平和垂直方向運動的動態范圍是相同的，那麼 Rx=Ry=R。估計的精度是由搜索的步長決定的，步長是相鄰兩個候選塊在水平或者垂直方向上的距離。通常，沿著兩個方向使用相同的步長。在最簡單的情況下，步長是一個像素，稱為整數像素精度搜索，該種演算法也稱為無損搜索演算法。 由於在窮盡塊匹配演算法中搜索相應塊的步長不一定是整數，一般來說，為了實現 1/K像素步長，對參考幀必須進行 K倍內插。根據實驗證明，與整像素精度搜索相比，半像素精度搜索在估計精度上有很大提高，特別是對於低清晰度視頻。
但是，應用分數像素步長，搜索演算法的復雜性大大增加，例如，使用半像素搜索，搜索點的總數比整數像素精度搜索大四倍以上。
那麼，如何確定適合運動估計的搜索步長，對於視頻編碼的幀間編碼來說，即使得預測誤差最小化。 快速搜索演算法和全局搜索演算法相比，雖然只能得到次最佳的匹配結果，但在減少運算量方面效果顯著。
1） 二維對數搜索法
這種演算法的基本思路是採用大菱形搜索模式和小菱形搜索模式，步驟如圖 6.4.20 所示，從相應於零位移的位置開始搜索，每一步試驗菱形排列的五個搜索點。下一步，把中心移到前一步找到的最佳匹配點並重復菱形搜索。當最佳匹配點是中心點或是在最大搜索區域的邊界上時，就減小搜索步長（菱形的半徑） 。否則步長保持不變。當步長減小到一個像素時就到達了最後一步，並且在這最
後一步檢驗九個搜索點。初始搜索步長一般設為最大搜索區域的一半。
其後這類演算法在搜索模式上又做了比較多的改進，在搜索模式上採用了矩形模式，還有六邊形模式、十字形模式等等。
2） 三步搜索法
這種搜索的步長從等於或者略大於最大搜索范圍的一半開始。第一步，在起始點和周圍八個 「1」標出的點上計算匹配誤差，如果最小匹配誤差在起始點出現，則認為沒有運動；第二步，以第一步中匹配誤差最小的點（圖中起始點箭頭指向的「1」）為中心，計算以「2」標出的 8個點處的匹配誤差。注意，在每一步中搜索步長搜都比上一步長減少一半，以得到更准確的估計；在第三步以後就能得到最終的估計結果，這時從搜索點到中心點的距離為一個像素。
但是，上述一些快速演算法更適合用於估計運動幅度比較大的場合，對於部分運動幅度小的場合，它們容易落入局部最小值而導致匹配精度很差，已經有很多各種各樣的視頻流證明了這一點。
現在，針對這一缺點，國內外諸多專家學者也提出了相應的應對措施，特別是針對H.264編碼標准要求的一些快速演算法的改進，並取得卓越的效果。例如[7]中提到的基於全局最小值具有自適應性的快速演算法，這種演算法通過在每一搜索步驟選擇多個搜索結果，基於這些搜索結果之間的匹配誤差的不同得到的最佳搜索點，因而可以很好地解決落入局部最小值的問題。
[8]中提到一種適用於H．264的基於自適應搜索范圍的快速運動估計演算法，經過實驗證明對於如salesman等中小運動序列，其速度可接近全局搜索演算法的400倍，接近三步搜索演算法的4倍；而對於大運動序列，如table tennis，該演算法則會自動調節搜索點數以適應復雜的運動。當從總體上考察速度方面的性能時，可以看到，該演算法平均速度是全局搜索演算法的287．4倍，三步搜索的2．8倍。 分級搜索演算法的基本思想是從最低解析度開始逐級精度的進行不斷優化的運動搜索策略，首先取得兩個原始圖象幀的金子塔表示，從上到下解析度逐級變細，從頂端開始，選擇一個尺寸比較大的數據塊進行一個比較粗略的運動搜索過程，對在此基礎上進行亞抽樣（即通過降低數據塊尺寸（或提高抽樣解析度）和減少搜索范圍的辦法）進行到下一個較細的級來細化運動矢量，而一個新的搜索過程可以在上一級搜索到的最優運動矢量周圍進行。在亞抽樣的過程中也有著不同的抽樣方式和抽樣濾波器。這種方法的優點是運算量的下降比例比較大，而且搜索的比較全面。
缺點是由於亞抽樣或者濾波器的採用而使內存的需求增加，另外如果場景細節過多可能會容易落入局部最小點。 由於物體的運動千變萬化，很難用一種簡單的模型去描述，也很難用一種單一的演算法來搜索最佳運動矢量，因此實際上大多採用多種搜索演算法相組合的辦法，可以在很大程度上提高預測的有效性和魯棒性。
事實上，在運動估計時也並不是單一使用上述某一類搜索演算法，而是根據各類演算法的優點靈活組合採納。在運動幅度比較大的情況下可以採用自適應的菱形搜索法和六邊形搜索法，這樣可以大大節省碼率而圖象質量並未有所下降。在運動圖象非常復雜的情況下，採用全局搜索法在比特數相對來說增加不多的情況下使得圖象質量得到保證。 H.264 編碼標准草案推薦使用 1/4分數像素精度搜索。[6]中提到在整像素搜索時採用非對稱十字型多層次六邊形格點運動搜索演算法，然後採用鑽石搜索模型來進行分數像素精度運動估計。
解碼器要求傳送的比特數最小化，而復雜的模型需要更多的比特數來傳輸運動矢量，而且易受雜訊影響。因此，在提高視頻的編碼效率的技術中，運動補償精度的提高和比特數最小化是相互矛盾的，這就需要我們在運動估計的准確性和表示運動所用的比特數之間作出折中的選擇。它的效果與選用的運動模型是密切相關的。

❷ 搜索技術

問題求解過程是 搜索答案（目標） 的過程，所以問題求解技術也叫做搜索技術——通過對 狀態空間 的搜索而求解問題的技術。

問題可形式化地定義成四個組成部分

在解題過程中 達到過的所有狀態 的集合。不同於狀態空間，搜索空間是其中一部分。狀態空間和搜索空間都屬於 過程性知識表示 。

八數碼問題詳解

兩種搜索技術

無信息搜索策略也稱 盲目搜索 ：沒有任何附加信息，只有生成後繼和區分目標和非目標狀態。
五種盲目搜索策略有：廣度優先搜索，代價一直搜索，深度優先搜索，深度有限搜索，迭代深入深度優先搜索。

從四種度量來評價廣度優先搜索

性能：通常使用遞歸函數實現，一次對當前節點的子節點調用該函數。相比廣度優先，內存需求少(分支因子 * 最大深度+1)。但 不是完備的也不是最優的 *。

深度優先搜索的無邊界問題可以通過提供一個 預先設定的深度限制I 來解決。深度=I的節點當作無後繼節點看待；雖然解決了無邊界問題，但 有可能無解 ； 如果選擇I>d則深度優先原則也不是最優解 。

每次改變限制深度 ，多次調用深度有限搜索，當 搜索到達最淺的目標節點深度 時就可以發現目標節點，稱為迭代深入深度優先搜索。這種搜索結合了廣度優先和深度優先兩種搜索方式的優勢。 解決了深度優先的完備性問題 。空間需求是(b * d),時間需求是(b d )。當搜索空間很大且深度未知時，迭代深入深度優先搜索 是首選的無信息搜索方式 。

迭代深入搜索中因為多次重復搜索上層節點，使部分狀態反復生成，看起來很浪費內存空間和時間。但是因為 在分支因子比較均衡的搜索樹 中， 多數節點都是葉子節點 *（葉子節點數遠大於上層節點總和），所以上層節點多次生成的影響並不大，與廣度優先相比，效率還是很高。

用於目標狀態已知，求解過程的問題。通常通過 廣度優先搜索 實現。從 起始節點和目標狀態兩個方向 開始擴展，當 兩個OPEN表出現交集 時表明搜索到了一條從起始到結果的一條路徑。 缺點 ：演算法編寫難。但一旦實現，效率要遠高於其他盲目搜索。

評價函數 ：f ( n ) = h ( n ) ；評價函數等於啟發函數
解釋：貪婪最佳優先搜索中 無條件選擇 當前離目標最近（代價最小）的結點進行擴展。但是 局部最佳不是全局最佳，即非最優。 其中h（ n ）稱為 啟發函數 ，是從節點n到目標節點的最低代價的 估計值 。

評價函數 ：f ( n ) = g ( n ) + h ( n )；評價函數等於啟發函數加路徑耗散函數
解釋：

另，對於有向圖的搜索還可以採用圖搜索方式。詳情： 圖搜索和樹搜索詳解

稱啟發函數是可採納的，如果h( n ) 滿足 h( n ) ≤ h * ( n ) ，其中 h * ( n )是從當前節點 n到達目標的最低真實代價 ，即h( n )的估值永遠小於真實耗散值；因為f ( n ) = g ( n ) + h ( n )，且g（n）為已知常數，所以 f（n）永遠不會高估經過結點n的解的實際代價 ，所以是最優解。

如果採用 A* 圖搜索演算法，則不一定返回最優解 。因為如果最優路徑不是第一個生成的，可能因為有重復狀態而被丟棄了。見上個鏈接： 圖搜索和樹搜索詳解

如果對於每個結點n，以及n的行為a產生的後繼結點n'滿足如下公式： h ( n ) ≤ c ( n, n', a) + h( n ') （c ( n, n', a)可以理解為g（n'）），則稱這個h ( n )啟發函數是一致的。

A* 搜索由初始結點出發開始搜索，以同心帶狀增長f（n）耗散值的方式擴展結點。如果h（n）= 0 意味著只按g（n）值排序，即同心帶為「圓形」。使用啟發函數則同心帶向目標節點拉伸（橢圓越來越扁）。

如果C*是最優路徑的耗散值，則：

A* 搜索的關鍵就是 設計可採納的或一致的（單調的）啟發函數 。

絕不高估 到達目標的耗散值，盡可能的接近真實耗散值

子問題的解耗散是完整問題的 耗散下界 。

從實例中學習，每個實例包含了解路徑上各狀態及其到達解的耗散值。每個最優解實例提供了可學習h(n)的實例，由此產生可預測其他狀態解消耗的啟發函數。

聯機搜索智能體需要行動和感知，然後擴展當前狀態的環境地圖

智能體初始位置在S，其已知信息為：

A* 搜索在不同子空間結點的跳躍式擴展， 模擬而非實際行動 ；聯機搜索只擴展實際占據的結點——採用深度優先。 聯機搜索必須維護一個回溯表

博弈搜索是智能體之間的對抗，每個智能體的目的是沖突的。本節需要解決兩個問題：如何搜索到取勝的 路徑 /如何提高搜索 效率 。相應的辦法是 極大極小決策和α-β剪枝 。

兩個智能體博弈時，可令一方為MAX，一方為MIN。MAX希望終局得分高，MIN希望終局得分低。

博弈搜索中，最優解是導致取勝的終止狀態的一系列招數。MAX制定取勝策略時，必須不斷考慮MIN應對條件下如何取勝。

如果博弈雙方 都按照最優策略 進行，則一個結點的 極大極小值就是對應狀態的效用值

簡單的遞歸演算法——按照定義計算每個後繼結點的極大極小值/搜索是從目標到初始結點的 反向推導

如果博弈樹最大深度為m，每個節點的合法招數為b，則

剪掉那些不可能影響最後決策的分支，返回和極大極小值相同的結果。
α-β剪枝可以應用樹的任何深度。

如果在結點n的父節點或更上層有一個更好的選擇m，則在搜索中永遠不會到達n。

很大程度上取決於檢查後繼節點的次序—— 應先檢查那些可能更好的後繼 。如果能先檢查那些最好的後繼，則 時間復雜度為O(b (d/2) ) 。優於極大極小演算法的O(b d )

許多問題中 路徑是無關緊要的 。從當前狀態出發，通常 只移動到相鄰狀態 ，且路徑不保留。

內存消耗少，通常是一個常數。

向目標函數值增加的方向持續移動，直到相鄰狀態沒有比它更高的值。 取到一個局部最優則終止 。
使新狀態估計值優於當前狀態值和其他所有候補結點值，則取新狀態放棄其他狀態。

將 爬山法 （停留在局部最優）和 隨機行走 （下山）以某種方式結合，同時擁有 完備性和效率 。
技巧是，概率足夠大可以彈出局部最優；但概率不能太大而彈出全局最優。

按照模擬退火的思想， T隨時間逐漸減小 。如果 T下降的足夠慢 ，則找到全局最優解是 完備的 。

隨機移動，如果評價值改善則採納； 否則以小於一的概率接受 。

從 k個隨機生成的狀態開始 ，每步生成k個結點的所有後繼狀態。如果其中之一是目標狀態則停止演算法；否則從全部後繼狀態中選擇最佳的k個狀態繼續搜索。
有用的信息 在k個並行的 搜索線程之間傳遞 ，演算法會很快放棄沒有成果的搜索，而把資源放在取得最大進展的搜索上。

局部剪枝搜索的變種。因為局部剪枝搜索搜索是貪婪的，因而用隨機剪枝搜索代替。不是選擇最好的k個後代，而是按照一定概率選取k個後繼狀態。

類似於自然界的選擇過程。狀態對應個體，其 值對應適應性 ，後代就是狀態。因此如果k個狀態缺乏多樣性，則局部搜索會受影響。

局部剪枝演算法已有 群體進化 （優勝劣汰）的趨勢。遺傳演算法是隨機剪枝的變種。

包括選擇，交叉和變異

又稱繁殖，按照一定的概率選擇兩對個體生成後繼狀態

計算每個個體i被選中的概率： pi = f(i) / [f(1)+...+f(n)] .然後根據概率將圓盤分為n個扇形，每個扇形大小為 2Πpi 。

繁殖過程中，後代是父串在雜交點上進行雜交得來的。這樣一來，後代子串保留了父串的優良特性又與父串不同。

首先以概率p隨機在種群中選擇pa和pb兩個個體，再從{1,2,...,m}中（可以按一定概率，如兩邊概率小於中間概率）選擇一個數i，作為交叉點。而後將兩個個體的交叉點後面的部分交換。

在新生成的後繼狀態中各個位置都會按照一個 獨立的很小的概率 隨機變異。
變異時要做到 一致變異 ；即相同概率地變異所有個體的每一位。

結合了「上山」和隨機行走，並在並行搜索線程之間交換信息。遺傳演算法的 最大優點在於雜交 。因為雜交可以 將獨立發展的若干個磚塊組合起來 ，提高搜索的粒度。

個體編碼某些位置上數字仍未確定的一個狀態子串。

如果 一個模式的實例的平均適應值超過均值 ，則種群內這個模式的實例數量會隨時間而增長（優勝）；反之則減少（劣汰）

長度較短，高於平均適應度的模式在遺傳運算元的作用下， 相互結合 ，能生成長度較長、適應度較高的 模式 。

Constraint Satisfying Problem，CSP。

由一個 變數集合{X1~Xn} 和一個 約束集合{C1~Cn} ；每個變數都有一個 非空可能的值域Di 。每個約束指定了 若干變數的一個子集內各變數的賦值范圍 。

CSP的一個狀態是，對一些或每個變數賦值

一組既是 相容賦值 又是 完全賦值 的對變數的賦值就是CSP的解。

提前考慮某些約束，以減少搜索空間

若X被賦值，檢查與X相連的Y，判斷是否滿足約束，去掉Y中不滿足約束的賦值。（進行某種檢驗，可以不為有問題的Y集合賦值 ）

❸ 搜索演算法的應用案例

(1)題目：黑白棋游戲
黑白棋游戲的棋盤由4×4方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構成一個游戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對於給定的初始游戲狀態和目標游戲狀態，編程計算從初始游戲狀態變化到目標游戲狀態的最短著棋序列。
(2)分析
這題我們可以想到用深度優先搜索來做，但是如果下一步出現了以前的狀態怎麼辦？直接判斷時間復雜度的可能會有點大，這題的最優解法是用廣度優先搜索來做。我們就可以有初始狀態按照廣度優先搜索遍歷來擴展每一個點，這樣到達目標狀態的步數一定是最優的（步數的增加時單調的）。但問題是如果出現了重復的情況我們就必須要判重，但是樸素的判重是可以達到狀態數級別的，其實我們可以考慮用hash表來判重。
Hash表：思路是根據關鍵碼值進行直接訪問。也就是說把一個關鍵碼值映射到表中的一個位置來訪問記錄的過程。在Hash表中，一般插入，查找的時間復雜度可以在O（1）的時間復雜度內搞定。對於這一題我們可以用二進制值表示其hash值，最多2^16次方，所以我們開個2^16次方的表記錄這個狀態出現沒有，這樣可以在O（1）的時間復雜度內解決判重問題。
進一步考慮：從初始狀態到目標狀態，必定會產生很多無用的狀態，那還有什麼優化可以減少這時間復雜度？我們可以考慮把初始狀態和目標狀態一起擴展，這樣如果初始狀態的某個被擴展的點與目標狀態所擴展的點相同時，那這兩個點不用擴展下去，而兩個擴展的步數和也就是答案。
上面的想法是雙向廣度優先搜索：
就像圖二一樣，多擴展了很多不必要的狀態。
從上面一題可以看到我們用到了兩種優化方法，即Hash表優化和雙向廣搜優化。一般的廣度優先搜索用這兩個優化就足以解決。

❹ 常見查找和排序演算法

查找成功最多要n 次，平均（n+1）/2次， 時間復雜度為O(n) 。
優點：既適用順序表也適用單鏈表，同時對表中元素順序無要求，給插入帶來方便，只需插入表尾即可。
缺點：速度較慢。

改進：在表尾設置一個崗哨，這樣不用去循環判斷數組下標是否越界，因為最後必然成立。

適用條件：

二分查找的判定樹不僅是二叉排序樹，而且是一棵理想平衡樹。 時間復雜度為O(lbn) 。

循環實現

遞歸實現

待排序的元素需要實現 Java 的 Comparable 介面，該介面有 compareTo() 方法，可以用它來判斷兩個元素的大小關系。

從數組中選擇最小元素，將它與數組的第一個元素交換位置。再從數組剩下的元素中選擇出最小的元素，將它與數組的第二個元素交換位置。不斷進行這樣的操作，直到將整個數組排序。

選擇排序需要 ~N2/2 次比較和 ~N 次交換，==它的運行時間與輸入無關==，這個特點使得它對一個已經排序的數組也需要這么多的比較和交換操作。

從左到右不斷 交換相鄰逆序的元素 ，在一輪的循環之後，可以讓未排序的最大元素上浮到右側。

在一輪循環中，如果沒有發生交換，那麼說明數組已經是有序的，此時可以直接退出。

每次都 將當前元素插入到左側已經排序的數組中 ，使得插入之後左側數組依然有序。

對於數組 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交換相鄰元素，令逆序數量減少 1，因此插入排序需要交換的次數為逆序數量。

==插入排序的時間復雜度取決於數組的初始順序，如果數組已經部分有序了，那麼逆序較少，需要的交換次數也就較少，時間復雜度較低==。

對於大規模的數組，插入排序很慢，因為它只能交換相鄰的元素，每次只能將逆序數量減少 1。希爾排序的出現就是為了解決插入排序的這種局限性，它通過交換不相鄰的元素，每次可以將逆序數量減少大於 1。

希爾排序使用插入排序對間隔 h 的序列進行排序。通過不斷減小 h，最後令 h=1，就可以使得整個數組是有序的。

希爾排序的運行時間達不到平方級別，使用遞增序列 1, 4, 13, 40, ... 的希爾排序所需要的比較次數不會超過 N 的若干倍乘於遞增序列的長度。後面介紹的高級排序演算法只會比希爾排序快兩倍左右。

歸並排序的思想是將數組分成兩部分，分別進行排序，然後歸並起來。

歸並方法將數組中兩個已經排序的部分歸並成一個。

將一個大數組分成兩個小數組去求解。

因為每次都將問題對半分成兩個子問題，這種對半分的演算法復雜度一般為 O(NlogN)。

先歸並那些微型數組，然後成對歸並得到的微型數組。

取 a[l] 作為切分元素，然後從數組的左端向右掃描直到找到第一個大於等於它的元素，再從數組的右端向左掃描找到第一個小於它的元素，交換這兩個元素。不斷進行這個過程，就可以保證左指針 i 的左側元素都不大於切分元素，右指針 j 的右側元素都不小於切分元素。當兩個指針相遇時，將切分元素 a[l] 和 a[j] 交換位置。

快速排序是原地排序，不需要輔助數組，但是遞歸調用需要輔助棧。

快速排序最好的情況下是每次都正好將數組對半分，這樣遞歸調用次數才是最少的。這種情況下比較次數為 CN=2CN/2+N，復雜度為 O(NlogN)。

最壞的情況下，第一次從最小的元素切分，第二次從第二小的元素切分，如此這般。因此最壞的情況下需要比較 N2/2。為了防止數組最開始就是有序的，在進行快速排序時需要隨機打亂數組。

因為快速排序在小數組中也會遞歸調用自己，對於小數組，插入排序比快速排序的性能更好，因此在小數組中可以切換到插入排序。

最好的情況下是每次都能取數組的中位數作為切分元素，但是計算中位數的代價很高。一種折中方法是取 3 個元素，並將大小居中的元素作為切分元素。

對於有大量重復元素的數組，可以將數組切分為三部分，分別對應小於、等於和大於切分元素。

三向切分快速排序對於有大量重復元素的隨機數組可以在線性時間內完成排序。

快速排序的 partition() 方法，會返回一個整數 j 使得 a[l..j-1] 小於等於 a[j]，且 a[j+1..h] 大於等於 a[j]，此時 a[j] 就是數組的第 j 大元素。

可以利用這個特性找出數組的第 k 大的元素。

該演算法是線性級別的，假設每次能將數組二分，那麼比較的總次數為 (N+N/2+N/4+..)，直到找到第 k 個元素，這個和顯然小於 2N。

堆中某個節點的值總是大於等於其子節點的值，並且堆是一顆完全二叉樹。

堆可以用數組來表示，這是因為堆是完全二叉樹，而完全二叉樹很容易就存儲在數組中。位置 k 的節點的父節點位置為 k/2，而它的兩個子節點的位置分別為 2k 和 2k+1。這里不使用數組索引為 0 的位置，是為了更清晰地描述節點的位置關系。

在堆中，當一個節點比父節點大，那麼需要交換這個兩個節點。交換後還可能比它新的父節點大，因此需要不斷地進行比較和交換操作，把這種操作稱為上浮。

類似地，當一個節點比子節點來得小，也需要不斷地向下進行比較和交換操作，把這種操作稱為下沉。一個節點如果有兩個子節點，應當與兩個子節點中最大那個節點進行交換。

將新元素放到數組末尾，然後上浮到合適的位置。

從數組頂端刪除最大的元素，並將數組的最後一個元素放到頂端，並讓這個元素下沉到合適的位置。

把最大元素和當前堆中數組的最後一個元素交換位置，並且不刪除它，那麼就可以得到一個從尾到頭的遞減序列，從正向來看就是一個遞增序列，這就是堆排序。

一個堆的高度為logN，因此在堆中插入元素和刪除最大元素的復雜度都為 logN。

對於堆排序，由於要對 N 個節點進行下沉操作，因此復雜度為 NlogN。

堆排序是一種原地排序，沒有利用額外的空間。

現代操作系統很少使用堆排序，因為它無法利用局部性原理進行緩存，也就是數組元素很少和相鄰的元素進行比較和交換。

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，==計數排序要求輸入的數據必須是有確定范圍的整數==。

當輸入的元素是 n 個 0 到 k 之間的整數時，它的==運行時間是 O(n + k)==。計數排序不是比較排序，排序的速度快於任何比較排序演算法。由於用來計數的數組C的長度取決於待排序數組中數據的范圍（等於待排序數組的最大值與最小值的差加上1），這使得計數排序對於數據范圍很大的數組，需要大量時間和內存。比較適合用來排序==小范圍非負整數數組的數組==。

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在於這個映射函數的確定。為了使桶排序更加高效，我們需要做到這兩點：

同時，對於桶中元素的排序，選擇何種比較排序演算法對於性能的影響至關重要。

當輸入數據均勻分配到每一個桶時最快，當都分配到同一個桶時最慢。

實間復雜度N*K

快速排序是最快的通用排序演算法，它的內循環的指令很少，而且它還能利用緩存，因為它總是順序地訪問數據。它的運行時間近似為 ~cNlogN，這里的 c 比其它線性對數級別的排序演算法都要小。

使用三向切分快速排序，實際應用中可能出現的某些分布的輸入能夠達到線性級別，而其它排序演算法仍然需要線性對數時間。

❺ 怎樣才能快速搜索路由表有哪些著名的搜索演算法

有三個路由器，a，b和c。路由器a的兩個網路介面f0和s0
分別連接在
10.1.0.0和10.2.0.0網段上；路由器b的兩個網路介面s0和s1
分別連接在
10.2.0.0和10.3.0.0網段上；路由器c的兩個網路介面s0和e0
分別連接在
10.3.0.0和10.4.0.0網段上；
如上圖中各路由表的前兩行所示，通過路由表的網路介面到與之直接相連的網
絡的網路連接，其向量距離設置為0。這即是最初的路由表。
當路由器b和a以及b和c之間相互交換路由信息後，它們會更新各自的路由表。
例如，路由器b通過網路埠s1收到路由器c的路由信息（10.3.0.0,s0,0）和(10.4.0.0,e0,0)後，在自己的路由表中增加一條(10.4.0.0,s1,1)路由信息。該信息表示：通過路由器b的網路接
口s1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器c的基礎上加1獲得的。
同樣道理，路由器b還會產生一條(10.1.0.0,s0,1)路由，這條路由是通過網路埠s0從路由器a
獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。
概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由
器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路
由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條
新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的
向量距離與更新信息中的向量距離相加作為新路由的向量距離。

❻ 在用鄰接表表示圖時,對圖進行深度優先搜索遍歷的演算法的時間復雜度為()

因為當相鄰矩陣的大部分被破壞時，矩陣中的所有元素都需要掃並追蹤到，且元素個數為n＾2，自然演算法為O（n＾2）。

所以鄰接表只存儲邊或弧，如果掃描鄰接表，當然會得到O（n＋e）其中n是頂點的數量，e的邊或弧的數量。

設有n個點，e條邊

鄰接矩陣：矩陣包含n＾2個元素，在演算法中共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為O（n＾2）。

鄰接表：包含n個頭結點和e個表結點，演算法中對所有結點都要遍歷一次，所以時間復雜度為O（n+e）順便，對於廣度優先演算法的時間復雜度，也是這樣。

(6)相鄰搜索演算法擴展閱讀：

鄰接表是圖的最重要的存儲結構之一，描述了圖上的每個點。創建一個容器對於每一個圖的頂點（n頂點n容器）和節點在第i個容器包含所有相鄰頂點的頂點Vi。事實上，我們經常使用的鄰接矩陣是一個鄰接表的邊集不離散化每一個點。

在有向圖中，描述每個點與另一個節點連接的邊(在a點->點B)。

在無向圖中，描述每個點上的所有邊（A點和B點的情況）

鄰接表對應的圖存儲方法稱為邊集表。此方法將所有邊存儲在容器中。