预期的最大值
不守规矩
我有的是算法，它将数组作为参数，并返回其最大值。
find_max(as) :=
max = as[0]
for i = 1 ... len(as) {
if max < as[i] then max = as[i]
}
return max
我的问题是：假设数组最初是（均匀）随机排列的，并且其所有元素都是不同的，那么max变量被更新的预期次数是多少（忽略初始赋值）。
例如，如果为as = [1, 3, 2]，则对的更新数max将为1（读取值3时）。
用户名
实证解决方案
可以执行和分析许多不同阵列大小的仿真，并进行多次试验：
#include <iostream>
#include <fstream>
#include <cstdlib>
#define UPTO 10000
#define TRIALS 100
using namespace std;
int arr[UPTO];
int main(void){
ofstream outfile ("tabsep.txt");
for(int i = 1; i < UPTO; i++){
int sum = 0;
for(int iter = 0; iter < TRIALS; iter++){
for(int j = 0; j < i; j++){
arr[j] = rand();
}
int max = arr[0];
int times_changed = 0;
for(int j = 0; j < i; j++){
if (arr[j] > max){
max = arr[j];
times_changed++;
}
}
sum += times_changed;
}
int avg = sum/TRIALS;
outfile << i << "\t" << avg << "\n";
cout << "\r" << i;
}
outfile.close();
cout << endl;
return 0;
}
当我绘制这些结果的图形时，复杂度似乎是对数的：
我认为可以断定时间复杂度为O（log n）是安全的。
理论解决方案：
- 假设数字在0 ... n范围内
- 您有一个暂定的最大值
- 下一个最大值将是m + 1 ... n范围内的随机数，其平均值为（m + n）/ 2
- 这意味着，每次找到新的最大值时，都将可能的最大值范围除以2
- 重复除法等于对数
- 因此，找到新的最大值的次数为O（log n）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
varchar的最大值
- 2
每行的最大值
- 3
AND运算的最大值
- 4
每行的最大值
- 5
JTextField的最大值
- 6
计算最大值
- 7
选择的最大值
- 8
为什么reduce {}不能按预期返回最大值？
- 9
PHP-查找最大值/最大值
- 10
在matlab中检查交替最大值最大值
- 11
选择最大值而不使用最大值？
- 12
更新范围的最大值
- 13
列中的最大值
- 14
angularjs $超时最大值
- 15
打印INT的最大值
- 16
Postgres BIGINT的最大值
- 17
R的逐行最大值
- 18
SQL获得最大值
- 19
java int的最大值
- 20
收集多个最大值
- 21
ADFS TokenLifeTime最大值？
- 22
计算逐行最大值
- 23
获取列的最大值
- 24
QueryDSL返回最大值
- 25
Mathematica列表的最大值
- 26
选择多个最大值
- 27
阵列的最大值（SAS）
- 28
从RichTextBox获取最大值
- 29
选择列的最大值
我来说两句