平均查找長度

為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數的數學期望值稱為查找算法在查找成功時的平均查找長度，ASL成功。

對於含有n個數據元素的查找表，查找成功的平均查找長度為：ASL=∑PiCi (i=1,2,3,…,n),可以簡單以數學上的期望來這麼理解。其中：Pi 為查找表中第i個數據元素的概率，Ci為找到第i個數據元素時已經比較過的次數。

在查找表中查找不到待查元素，但是找到待查元素應該在表中存在的位置的平均查找次數稱為查找不成功時的平均查找長度，不成功。