algorithm - Average-case算法分析

Question

我正在尝试解决一个非常简单的算法分析(显然对我来说不是那么简单)。

算法是这样的:

int findIndexOfN(int A[], int n) {
// this algorithm looks for the value n in array with size of n.
// returns the index of n in case found, otherwise returns -1.
// it is possible that n doesn't appear in the array.
// n appears at most one time.
// the probability that n doesn't appear in the array is $1/(n+1)$
// for each cell in the array, the probability that n is found in index i
// is $1/(n+1)$


    int index, fIndex;
    index = 0;
    fIndex = -1;
    while (index < n && fIndex == -1) {
      if(A[index] == n) {
        fIndex = index;
      }
      index++;
    }
    return fIndex;

 }

现在我正在尝试计算平均运行时间。我认为这是几何级数，但我找不到合并概率和复杂性这两个术语的方法。

例如，我知道如果在索引 1 中找到值 n，则需要 1 个循环步骤来获取第二个索引 (1) 并找到 n。

另一方面，概率给了我一些分数....

这是我到目前为止得到的:

$\sigma 从 i=1 到 n 计算 ( (1/n) * ((n-1)/n)^i-1 )

但同样，我找不到这个公式与 T(n) 的联系，也找不到这个函数与 BigOh、BigOmega 或 Theta 的关系。

Answer 1

这个算法就是BigOh(n)、BigOmega(n)和Theta(n)。

要了解这一点，您不需要计算概率或使用主定理(因为您的函数不是递归的)。您只需要看到该函数就像是 n 项的循环。如果您这样表示您的功能，也许会更容易:

for (int i = 0; i < n; ++i) {
    if (A[i] == n)
        return i;
}

我知道这似乎违反直觉，因为如果 n 是数组的第一个元素，实际上您只需要一个操作就可以找到它。这里重要的是一般情况，其中n 位于数组中间的某个位置。

让我们这样说吧:给定你写的概率，n 有 50% 的可能性在元素 n/4 和 3n/4 之间 你的数组。在这种情况下，您需要在 n/4 和 3n/4 之间进行测试以找到您的元素，该元素的计算结果为 O(n)(您当你做 BogOh 分析时去掉常量)。

如果您想知道您需要的平均操作次数，您可以计算一个序列，就像您在问题中写的那样。给你平均操作次数的实际系列是

1/(n+1) + 2/(n+1) + 3/(n+1) ... + n/(n+1)

为什么？因为您需要一次测试 n 是否在第一个位置(概率为 1/(n+1))，如果 n 是则需要两次测试在第二个位置(概率为 1/(n+1))，... i 测试 n 是否在 中第 i 个位置(概率 1/(n+1))

这个系列评估为

n(n+1)/2 * 1/(n+1) = n/2