在数组中找到最小值所需的赋值次数？
有人问我一个脑筋急转弯，我不知道；我的知识在分期分析后变慢了，在这种情况下，这是O(n)。
public int findMax(array) {
int count = 0;
int max = array[0];
for (int i=0; i<array.length; i++) {
if (array[i] > max) {
count++;
max = array[i];
}
}
return count;
}对于大小为n的数组，count的期望值是多少？
数字是从均匀分布中随机选取的。
回答 4
Stack Overflow用户
发布于 2011-07-19 00:06:39
设f(n)是赋值的平均数。
如果最后一个元素不是最大的，则f(n) = f(n-1)。
如果最后一个元素是最大的，则f(n) = f(n- 1 ) +1。
由于最后一个数字是概率为1/n的最大数，而不是概率为(n-1)/n的最大数，因此我们有：
f(n) = (n-1)/n*f(n-1) + 1/n*(f(n-1) + 1)展开并收集术语以获取：
f(n) = f(n-1) + 1/nf(1) = 0。所以：
f(1) = 0
f(2) = 0 + 1/2
f(3) = 0 + 1/2 + 1/3
f(4) = 0 + 1/2 + 1/3 + 1/4也就是说，f(n)是只能以闭合形式approximately获得的n_th“调和数”。(嗯，比n_th调和数少一。如果您将max初始化为INT_MIN并让循环运行，这样f(1) =1，问题会更好一些。)
以上不是一个严格的证明，因为我对预期值和实际值的判断很草率。但我相信答案是正确的:-)。
Stack Overflow用户
发布于 2011-07-19 00:53:58
我想对Nemo的回答发表评论，但我没有名气来评论。他的正确答案可以简化为：
第二个数大于第一个数的概率是1/2。尽管如此，第三个数大于2的概率是1/3。这些都是独立的概率，因此总的期望值是
1/2 + 1/3 + 1/4 + ..+ 1/n
Stack Overflow用户
发布于 2011-07-19 04:09:48
实际上，当每一项的值来自有限集时，您可以进一步进行这种分析。设E(N，M)是在从大小为M的字母表中找出N个元素的最大值时的期望赋值数，然后我们可以说…
E(0, M) = E(N, 0) = 0
E(N, M) = 1 + SUM[SUM[E(j, i) * (N - 1 Choose j) * ((M - i) / M)^(N-j-1) * (i / M) ^ j : j from 0 to N - 1] : i from 0 to M - 1]这有点难想出一个封闭的形式，但我们可以确定E(N，M)在O(log(min(N，M)。这是因为E(N，INF)在θ( log (N))中，因为调和级数和与对数函数成正比增长，并且E(N，M) < E(N，M+ 1)。同样，当M
这里有一些自己计算E(N，M)的代码。我想知道有没有人能把这个写成封闭式的？
#define N 100
#define M 100
double NCR[N + 1][M + 1];
double E[N + 1][M + 1];
int main() {
NCR[0][0] = 1;
for(int i = 1; i <= N; i++) {
NCR[i][0] = NCR[i][i] = 1;
for(int j = 1; j < i; j++) {
NCR[i][j] = NCR[i - 1][j - 1] + NCR[i - 1][j];
}
}
for(int n = 1; n <= N; n++) {
for(int m = 1; m <= M; m++) {
E[n][m] = 1;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
E[n][m] += NCR[n - 1][j] *
pow(1.0 * (m - i) / m, n - j - 1) *
pow(1.0 * i / m, j) * E[j][i] / m;
}
}
}
}
cout << E[N][M] << endl;
}https://stackoverflow.com/questions/6735701
复制相似问题
腾讯云开发者
