我试图解决一个非常简单的算法分析(显然对我来说不是那么简单)。
算法如下:
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)并找到n。
另一方面概率给了我一些分数…
到目前为止我得到的是:
$\sigma从i=1到n evaluate((1/n)*((n-1)/n)^i-1)
但同样,我找不到这个公式与t(n)的关系,也找不到这个函数的BigOh,BigOmega或the t a的关系。
最佳答案
这个算法是bigoh(n)、bigomega(n)和theta(n)。
要知道这一点,您不需要计算概率或使用主定理(因为您的函数不是递归的)。你只需要看看这个函数就像一个循环。如果你像这样描述你的功能,也许会更容易些:
for (int i = 0; i < n; ++i) {
if (A[i] == n)
return i;
}
我知道这似乎违反直觉,因为如果
n
是数组的第一个元素,那么实际上只需要一个操作就可以找到它这里重要的是一般情况,其中n
位于数组的中间。让我们这样说:考虑到您所写的概率,有50%的可能性
n
在数组的元素n
和n/4
之间在这种情况下,您需要在3n/4
和n/4
测试之间找到您的元素,该元素的计算结果为3n/4
(在进行bogoh分析时,您会删除常数)。如果你想知道你需要的平均操作数,你可以计算一个系列,就像你在问题中写的那样给出平均操作数的实际序列是
1/(n+1) + 2/(n+1) + 3/(n+1) ... + n/(n+1)
为什么?因为如果
O(n)
在第一个位置(概率n
)需要一个测试,如果1/(n+1)
在第二个位置(概率n
)需要两个测试,…1/(n+1)
测试i
是否位于n
第th个位置(概率i
)本系列评估为
n(n+1)/2 * 1/(n+1) = n/2