algorithm - 为什么在这个方程中是 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 first 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在每个位置使用 SequentialSearch 均一律等于 p/n这将是一个相当奇怪的假设，因为这意味着 K 的概率。实际发生在每个位置并不是均匀分布的。
确实，如果K在数组中多次出现，只有第一次出现会被 SequentialSearch 找到，所以 K 的值位于数组末尾的位置永远不会在复杂度计算中起作用。如果我们让 K在数组中多次出现，较早出现的相对权重必须更高，因此提前终止的概率必须高于找到第一次出现 K 的概率。在最后一个位置。
然而，正如我们稍后会在许多介绍性教科书中发现的那样，该算法是在假设我们遇到的第一个插槽 K 的情况下进行分析的。在数组中可能以相等的概率出现在数组的任何位置。这可能是因为公式更容易推导。但是坚持住。
相反，在数组算法的非教科书复杂度分析中，我们假设数组中的每个槽都是一个独立变量，具有相同的概率取任何可接受的值。在概率论中，这种服从相同概率分布的独立随机变量序列通常被称为伯努利试验。
使用独立随机变量进行分析
假设数组中的每个槽可以独立地取值 K等概率q .然后可以使用伯努利公式计算 n 次独立试验的成功搜索概率。它给:

这意味着

所以p仅约等于 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 by Sequential Search 在第二个槽中也等于 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 呈现的公式