为什么在这个方程中是 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

如果使用顺序搜索K在每个位置遇到的概率一致等于，这将是一个相当奇怪的假设，因为这意味着每个位置实际发生的概率不是均匀分布的。p/nK

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

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

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

独立随机变量分析

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

这意味着

Sop仅约等于q * n且近似误差随 快速增长n。

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

使用算术几何级数之和的公式并代入 ，1-p我们(1 - q)^n可以简化这个表达式：

得到的公式看起来与教科书上的公式不同。

现在我们可以尝试通过实验来检查哪个公式是正确的。下面是结果图以及用于生成该图数据的 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 只能保存c与两者都不同的值a和b，等等。

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

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

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

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

《算法设计与分析导论》教科书引用了Van Gelder 和 Baase 的《计算机算法：设计与分析导论》，他们在没有任何计算的情况下得出了相同的公式。他们只是说：如果我们搜索一个长度为 的数组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

教科书公式给出

在不同值的情况下，我们只有 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.

这里教科书的公式是正确的：

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

结论

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

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

* 使用QuickLaTeX渲染的公式