2. 无序线性表中的查找分析¶
2.1. 无序线性表中的查找分析¶
你已经知道最简单的查找形式：顺序查找算法。 在无序线性表上进行顺序查找，最坏、平均、最好情况下都需要 \(\Theta(n)\) 时间。 关于查找无序线性表，似乎要说的话就这么多。 但仍有一些需要考虑之处，比如我们的模型应当如何处理元素根本不在线性表中的情况，以及如何对这条"显而易见"的下界做出真正正确的证明。
线性搜索平均需要进行多少次比较？一个主要考虑因素是 \(K\) 是否根本不在列表 L 中。我们可以通过忽略输入中除 \(K\) 在 L 中被找到时的位置之外的所有信息来简化分析。因此，我们有 \(n+1\) 种不同的可能事件： \(K\) 位于 L 中从 0 到 \(n-1\) 的某个位置（每个位置都有其自身的概率），或者它根本不在 \(L\) 中。我们可以将 \(K\) 不在 L 中的概率表示为
其中 \(\mathbf{P}(x)\) 是事件 \(x\) 的概率。
设 \(p_i\) 为 \(K\) 位于 L 的位置 \(i\) （下标从 0 到 \(n-1\)）的概率。 对线性表中的任何位置 \(i\)，标准顺序查找将查看 \(i+1\) 条记录。 因此我们说，当 \(K\) 位于位置 \(i\) 时代价为 \(i+1\)。 当 \(K\) 不在 L 中时，顺序查找需要 \(n\) 次比较。 设 \(p_n\) 为 \(K\) 不在 L 中的概率。 那么平均代价 \(\mathbf{T}(n)\) 为
如果我们假设所有 \(p_i\) （除 \(p_n\) 外）都相等，等式会变成什么样？
取决于 \(p_n\) 的取值（它可以从 0 变到 1），\(\frac{n+1}{2} \leq \mathbf{T}(n) \leq n\)。
2.1.1. 下界证明¶
给定一个（无序）线性表 L，包含 \(n\) 个元素和一个查找键 \(K\)，我们试图在 L 中识别出键值为 \(k\) 的一个元素（如果存在的话）。 在接下来的讨论中，我们将假设 L 中元素的键值互不相同，所有可能键构成的集合是全序的（也就是说，对任意一对键值都定义了运算 \(<\)、\(=\) 和 \(>\)），并且比较是我们确定两个键相对顺序的唯一途径。 我们的目标是用最少的比较次数来解决问题。
基于这个查找定义，我们很容易得出标准的顺序查找算法，同时也能看出这个问题的下界"显然"是 \(n\) 次比较。 （请记住，键 \(K\) 可能实际上不会出现在线性表中。） 然而，下界证明有一点滑头，看看它们是怎样出错的，是很有教益的。
下面是我们证明该定理的第一次尝试。
这个证明正确吗？ 虽然这对"标准"的从左到右线性查找算法成立，但希望你能够比较清楚地看出，并非所有算法都必须按这一特定顺序遍历线性表， 因此并非所有算法都必须最后查看位置 L [\(n\)]。
好吧，那么我们可以试着把证明修饰得灵活一些。
这个证明正确吗？仍然不对。 首先，任何给定算法在其 \(n-1\) 次查找中都不必始终如一地跳过某个给定位置 \(i\)。 例如，并不是所有算法都必须从左到右查找线性表。 甚至并不是所有算法每次遍历线性表时都必须先查找同样的 \(n-1\) 个位置。 也许它是用 0 到 \(n-1\) 各位置的一个随机排列来挑选这些位置的。
同样，我们可以试着把证明修饰成下面这样。
遗憾的是，这个证明还存在另一个需要修正的错误。 并非所有解决该问题的算法都必须通过把 L 中的元素直接与 \(K\) 比较来工作。 算法也许可以通过把 L 中的元素互相比较来取得有意义的进展。 例如，如果我们比较 L 中的两个元素，再把较大的那个与 \(K\) 比较，如果发现该元素小于 \(K\)，我们就知道另一个元素也小于 \(K\)。 凭直觉似乎很明显，这样的比较实际上不会带来更快的算法，但我们如何确定呢？ 我们需要以某种方式推广这个证明，把这种方法考虑进去。
下面我们给出一个有用的抽象，用来表示一组对象之间值的关系的知识状态。 全序 定义一个对象集合内的关系，使得对于任意两个对象，总有一个大于另一个。 偏序集 或 偏序集 是只在其上定义了部分序的集合。 也就是说，可能存在这样一对元素：我们无法判定其中哪一个"更大"。 出于此处的目的，部分序就是我们当前对对象的知识状态，其中元素对之间的序关系已知零个或多个。 我们可以通过绘制表示已知关系的有向无环图（DAG）来表示这方面的知识，如下面的幻灯片所示。
