10.2. 无序线性表中的查找分析¶
10.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\)。
10.2.1.1. 下界证明¶
给定一个含 \(n\) 个元素的（无序）线性表 L 和一个查找键 \(K\)，我们想在 L 中找出一个键值为 \(k\) 的元素（如果存在的话）。在接下来的讨论中，我们假设 L 中元素的键值互不相同，所有可能的键构成全序集（即对任意两个键值都定义了运算 \(<\)、\(=\) 和 \(>\)），并且比较是判断两个键相对顺序的唯一手段。目标是使用尽可能少的比较次数来解决问题。
给定查找的这种定义，我们很容易给出标准的顺序查找算法，同时也不难看出该问题的下界"显然"是 \(n\) 次比较。（请记住，键 \(K\) 未必真的出现在线性表中。）不过，下界证明多少有些微妙，看看它们会在哪里出错很有启发。
下面是我们证明该定理的第一次尝试。
这个证明正确吗？对"标准"的从左到右顺序查找算法来说它成立，但你应该能相当清楚地看出：并非所有算法都非得按这一特定顺序遍历线性表，因此也并非所有算法都非得最后才查看位置 L [\(n\)]。
好吧，那么我们可以试着把证明修饰得灵活一些。
这个证明正确吗？仍然不对。首先，一个算法在它的 \(n-1\) 次查找中，未必总是跳过同一个位置 \(i\)。例如，并非所有算法都从左到右查找线性表；也并非所有算法每次遍历时都先查找同样的 \(n-1\) 个位置——它可能是按 0 到 \(n-1\) 这些位置的一个随机排列来挑选的。
同样，我们可以试着把证明修饰成下面这样。
遗憾的是，这个证明还有另一个错误需要修正。并非所有求解该问题的算法都只能靠把 L 中的元素直接与 \(K\) 比较来进行。算法的进展也可能来自把 L 中的元素两两比较。例如，先比较 L 中的两个元素，再把其中较大的与 \(K\) 比较；如果发现它小于 \(K\)，我们就知道另一个元素也小于 \(K\)。直觉上，这样的比较似乎不会带来更快的算法，但我们凭什么断定呢？我们需要设法推广这个证明，把这种思路也考虑进去。
下面我们给出一种有用的抽象，用来表示"一组对象之间大小关系"的已知状态。 全序 为对象集合内的元素定义了这样的关系：任意两个对象中总有一个大于另一个。 偏序集 或 偏序集 则是只定义了偏序的集合，也就是说，可能存在这样两个元素，我们无法判定哪个"更大"。在这里，偏序代表我们目前对这些对象已知的信息状态，即元素两两之间的序关系有多少已经知道。我们可以用有向无环图（DAG）画出已知关系来表示这种信息，如下面的幻灯片所示。
