我正在尝试解决一个非常简单的算法分析(显然对我来说不是那么简单)。
算法是这样的:
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 的关系。