为什么 p/n 在这个等式中？

Question

Introduction to the Design and Analysis of Algorithms一书中，提供了该算法的伪代码，并分析了其平均效率：

ALGORITHM SequentialSearch(A[0..n − 1], K)
  //Searches for a given value in a given array by sequential   search 
  //Input: An array A[0..n − 1] and a search key K
  //Output: The index of the ﬁrst element in A that matches K
  // or −1 if there are no matching elements
  i ← 0
  while i < n and A[i] != K do
    i ← i + 1
  if i < n return i
  else return −1

然后这是平均情况下的效率，它分析并采用如下假设：

搜索成功的概率等于p(0≤p≤1)。
第一次匹配出现在第i个位置的概率每个 i

为什么 p/n 在那里？

Answer 1

n个位置中的每一个位置都有相同的概率成为第一个匹配项，并且K出现在任何地方的概率是p。所以每个位置必须有概率 p/n 成为第一个匹配项。

你也可以把第一行写成：

C_avg(n) = p(1/n + 2/n + 3/n + ... + n/n) + (1-p)n

在我看来，这更明显地区分了两种情况（找到 K 与未找到 K）。

Answer 2

如果使用 SequentialSearch 在每个位置遇到 K 的概率一致地等于 p/n 这将是一个相当奇怪的假设，因为这将意味着K实际出现在每个位置的概率不是均匀分布的。

确实，如果 K 在数组中出现多次，SequentialSearch 只会找到第一个，所以 K 的值位于进一步到数组的末尾将永远不会在复杂性计算中发挥作用。如果我们让 K 在数组中出现多次，则较早出现的相对权重必须更高，因此提前终止的概率必须高于找到第一次出现 K 的概率最后位置。

然而，正如我们稍后会在许多介绍性教科书中发现的那样，该算法是在假设我们遇到 K 的数组中的第一个位置可能以相等的概率出现在数组的任何位置的假设下进行分析的。这可能是因为公式更容易推导。但是等一下。

相反，在数组算法的非教科书复杂性分析中，我们假设数组中的每个槽都是一个独立变量，具有相同的概率取任何可接受的值。在概率论中，这种服从相同概率分布的独立随机变量序列通常被称为伯努利试验。

独立随机变量分析

假设数组中的每个槽可以独立地以等概率q取K的值。然后，可以使用伯努利公式计算 n 次独立试验的成功搜索概率。它给出：

$\Sigma_{k>0} \left(\begin{array}{c}n \ k\end{array}\right) q^k (1-q)^{n-k} = 1 - (1-q)^n = p$

这意味着

因此 p 仅约等于 q * n 并且近似误差随 n 快速增长。

在伯努利试验的情况下，平均复杂度的公式可以写成如下：

利用等差级数和的公式，用1-p代替(1 - q)^n，我们可以简化这个表达式：

$[ \begin{split} C_{\textrm{avg}} = q [ 1 + 2 (1-q) + \ldots + n (1-q)^{n-1} ] + n (1-q)^n\ = \frac{q}{1-q} [ (1-q) + 2(1-q)^2 + \ldots + n(1-q)^n] + n (1-q)^n \ = \frac{1}{q} [1 - (1-q)^n - nq(1-q)^n] + n (1-q)^n \ = \frac{1}{q} [p - nq(1-p)] + n (1-p) \end{split} ]$

生成的公式看起来与教科书上的公式不同。

现在我们可以尝试通过实验来检查哪个公式是正确的。下面是结果图和用于生成图数据的 Python 代码。参数 N_SIZES、N_TRIES 和 STEP 已从用于绘图的参数更改以更快地获得结果。

import csv 
import numpy as np

def generate_array(arr_size, max_value):
    random = np.random.randint(max_value, size=arr_size)
    return list(random)

def sequential_search(data_array, value_to_search):
    found = False
    try:
        result = data_array.index(value_to_search)
        found = True
    except ValueError:
        result = len(data_array)
    return found, result

def write_results(sizes, c_avg, p_avg):
    with open(f'cavg_{N_SIZES}_{N_TRIES}_{N_RANGE}.csv', 'w') as csvfile:
        csv.writer(csvfile).writerows(zip(sizes, c_avg, p_avg))

N_TRIES = 100 
N_SIZES = 1000
N_RANGE = 200
STEP = 10

def main():
    c_avg = []  # array to hold the average number of comparisons
    p_avg = []  # array to hold the frequency of success
    sizes = []  # array to hold array sizes

    for array_size in range(1, N_SIZES, STEP):
        value_to_search = np.random.randint(1, N_RANGE)
        success_rate = 0 
        c_avg_value = 0 
        for _tries in range(N_TRIES):
            arr = generate_array(array_size, N_RANGE)
            found, result = sequential_search(arr, value_to_search)
            if found:
                success_rate += 1
            c_avg_value += ((result * 1.0)/N_TRIES)
        c_avg.append(c_avg_value)
        p_avg.append((success_rate * 1.0)/N_TRIES)
    sizes.append(array_size)

    write_results(sizes, c_avg, p_avg)

if __name__ == '__main__':
    main()

总结一下。我想说这本教科书的分析在数组中值独立均等分布的假设下是不正确的。但这还不是全部。

当教科书上的公式正确时

不过也有课本分析成立的情况。假设我们有 M 个不同的实体。我们可以用数字 0 到 M-1 来识别它们。我们有 n 个插槽和 n < M。现在我们将实体随机分配给插槽，以便 M-n 个实体保持未分配状态。现在给定一个号码 K 我们要检查这个号码是否已分配到一个插槽。

此处成功的概率为 p = n/M 并且插槽中的值现在是相关的：如果插槽 1 分配了值 a，则插槽 2 只能保存值 b 与 a 不同，插槽 3 只能容纳与 a 和 b 不同的值 c，依此类推。

在第一个插槽中找到 K 的机会是 1/M，等于 p/n。现在在第二个插槽中通过顺序搜索找到 K 的机会也等于 1/M=p/n。如果你仔细想想，这似乎是显而易见的。

为了让我们相信这是正确的，让我们使用条件概率公式：

$[ \begin{align} P(\text{$K$ in slot 2}) & = P(\text{$K$ not in slot 1}) \cdot P(\text{$K$ in slot 2} | \text{$K$ not in slot 1}) \ & = \left(1 - \frac{1}{M}\right)\cdot \left(\frac{1}{M-1}\right)\ & = 1/M \end{align} ]$

我们可以通过归纳证明P(K in slot j) = 1/M对从1到n的每个j都成立。

因此我们可以使用教科书中的公式计算 SequentialSearch 的平均复杂度。

Introduction to the Design and Analysis of Algorithms 教科书引用了 Computer Algorithms: Introduction to Design and Analysis by Van Gelder and Baase where他们在没有任何计算的情况下得出相同的公式。他们只是说：如果我们搜索一个长度为 n 的数组，搜索的平均长度为 (n+1)/2，因此平均情况复杂度为

然而，这本教科书特别强调了数组中的所有元素都是不同的，因此不是独立的假设。

一个例子

如果您发现公式难以理解，那么可能没有比举个例子更好地说明这两种情况之间差异的方法了。

设取值范围M = 3、数组长度n = 2和K = 1.

在独立值的情况下，我们有以下9种可能性

Independent values
11       21       31
12       22       32
13       23       33

我们可以计算 SequentialSearch 的平均复杂度为

现在 p = 5/9 和 q = 1/3 所以新公式给出

$C_{\textrm avg} = \frac{1}{q} [p - nq(1-p)] + n (1-p) = 3 [\frac{5}{9} - 2\cdot \frac{1}{3}\cdot \frac{4}{9}] + 2\cdot\frac{4}{9} = 1\frac{2}{3}$

而教科书公式给出

$C_{\textrm avg} = p\frac{n+1}{2} + (1-p)n = \frac{5}{9}\cdot\frac{3}{2} + \frac{4}{9}\cdot 2 = \frac{31}{18}$

在不同值的情况下，我们只有 6 种可能性

distinct values
12       13       23
21       31       32

所以 p = 2/3 和 C_avg = 1/6 * (1 + 2 + 1 + 2 + 2 + 2) = 1 2/3.

此处教科书公式正确：

$C_{\textrm avg} = p\frac{n+1}{2} + (1-p)n = \frac{2}{3}\cdot\frac{3}{2} + \frac{1}{3}\cdot 2 = 1\frac{2}{3}$

令人惊讶的是，在不同值和独立值的假设下，平均复杂度是相同的，这是巧合。一般来说，这是不成立的。例如，考虑 M = 3, n = 3, K = 1 的情况。在这种情况下对于独立的值，我们得到 p = 19/27 和 C_avg = 2 1/9，对于不同的值，我们得到 p=1 和 C_avg = 2.

结论

现在由你来决定教科书上的公式是否是算法平均复杂度的正确解：

如果你认为数组中的值是独立的，那么你需要新的公式，
如果所有值都不同，那么您需要教科书中的公式。

* 使用 QuickLaTeX

呈现的公式

为什么 p/n 在这个等式中？

Why is p/n in this equation?

algorithm

average

time-complexity

独立随机变量分析

当教科书上的公式正确时

一个例子

结论