预期的最大数量

问题描述：

我有算法，它以数组作为参数，并返回其最大值。

I have is algorithm, which takes an array as an argument, and returns its maximum value.

find_max(as) :=
    max = as[0]
    for i = 1 ... len(as) {
        if max < as[i] then max = as[i]
   }
    return max

我的问题是：假设数组最初处于（统一）随机排列并且其所有元素都是不同的，那么 max 变量的预期次数是多少（忽略初始分配）。

My question is: given that the array is initially in a (uniformly) random permutation and that all its elements are distinct, what's the expected number of times the max variable is updated (ignoring the initial assignment).

例如，如果 as = [1,3,2] ，那么 max 的更新次数为1（读取值3时）。

For example, if as = [1, 3, 2], then the number of updates to max would be 1 (when reading the value 3).

答

经验解决方案

可以执行和分析许多不同阵列大小的模拟，每个阵列都有多个试验：

Empirical Solution

A simulation of many different array sizes with multiple trials each can be performed and analyzed:

#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;
}

当我绘制这些结果时，复杂性似乎是对数的：

When I graphed these results, the complexity appeared to be logarithmic:

我认为可以确定时间复杂度 O（log n）。

I think it's safe to conclude that the time complexity is O(log n).

假设数字在0 ... n

范围内你有一个暂定的最大值m

下一个最大值将是m + 1 ... n范围内的随机数，平均值为（m + n）/ 2

这意味着每次你找到一个新的最大值，你将可能的最大值范围除以2

重复除法相当于一个对数

因此a的次数找到新的最大值 O（log n）

Assume that the numbers are in the range 0...n
You have a tentative maximum m
The next maximum will be a random number in the range m+1...n, which averages out to be (m+n)/2
This means that each time you find a new maximum, you are dividing the range of possible maximums by 2
Repeated division is equivalent to a logarithm
Therefore the number of times a new maximum is found is O(log n)

经验解决方案

Empirical Solution

相关推荐