衡量检索算法知识点

二、衡量检索算法

评价一个检索算法的效率，需要在时间和空间两方面进行权衡。检索运算的主要操作是关键码值的比较，我们通常把检索过程中对关键码需要执行的平均比较次数，称为平均检索长度(Average Search Length)，它是衡量检索算法优劣的时间标准。显然平均检索长度是存储结构中对象总数n的函数，其定义为：

    其中，Pi为检索第i个元素（即给定值K与存储结构中第i个元素的关键码值相等）的概率，Ci为找到第i个元素所需的关键码值与给定值的比较次数。假设线性表为（a, b, c），检索a、b、c的概率分别为0.4、0.1、0.5，则顺序检索算法的平均检索长度为0.4×1+0.1×2+0.5×3 = 2.1，即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素。此外，我们还需要考虑不成功的检索。
    “检索第i个元素的概率P”可理解为：在很多次的检索中，找第i个元素的次数占总次数的比例为P。显然，若已知各个元素检索概率的分布情况，则ASL可准确地反映检索算法的平均时间性能。
    另外，衡量一个检索算法还要考虑算法所需的存储量、算法的复杂性等因素。