平均查找長度

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

基本介紹

• 中文名：平均查找長度
• 外文名：Average Search Length
• 簡稱：ASL
• 其他：不詳

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

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

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