1

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

算法是这样的：

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 的关系。

4

1 回答 1

1

该算法是 BigOh(n)、BigOmega(n) 和 Theta(n)。

要知道这一点，您不需要计算概率或使用主定理（因为您的函数不是递归的）。您只需要看到该函数就像是对n术语的循环。如果您像这样表示您的功能，也许会更容易：

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

我知道这似乎违反直觉，因为 ifn是数组的第一个元素，实际上您只需要一个操作即可找到它。这里重要的是一般情况，在n你的数组中间的某个地方。

让我们这样说：给定你写的概率，元素和数组n之间有 50% 的机会。在这种情况下，您需要 between和测试来找到您的元素，该元素的计算结果为（在进行 BogOh 分析时删除常量）。n/43n/4n/43n/4O(n)

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

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

为什么？因为您需要一个测试是否n在第一个位置（概率为1/(n+1)），两个测试是否n在第二个位置（概率为1/(n+1)），...i测试是否n在第ith 位置（概率为1/(n+1)）

该系列评估为

n(n+1)/2 * 1/(n+1) = n/2
于 2012-11-02T19:01:29.913 回答