预期的最大数量

Question

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

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时).

Answer 1

假设原始数组包含值1,2,...,N.

设X_i,i = 1..N是随机变量,如果i在算法期间的某个点处为最大值,则取值1.

然后算法采用的最大值数是随机变量:M = X_1 + X_2 + ... + X_N.

平均值(根据定义)E(M)= E(X_1 + X_2 + ... + X_N).使用期望的线性,这是E(X_1)+ E(X_2)+ .. + E(X_N),这是概率(1表示为最大值)+概率(2表示为最大值)+ ... +概率(N显示为最大值)(因为每个X_i取值0或1).

我什么时候出现最大值？它出现在i,i + 1,i + 2,...,N之间的数组中.它的概率是1 /(N-i + 1)(因为这些数字中的每一个都同样可能是第一).

所以...... prob(我出现最大值)= 1 /(N-i + 1),总体期望值是1/N + 1 /(N-1)+ .. + 1/3 + 1/2 + 1/1

这是谐波(N),其近似于ln(N)+ emc,其中emc~ = 0.5772156649,Euler-Mascheroni常数.

由于在该问题中您没有将最大值的初始设置计数为第一个值作为一个步骤,因此实际答案是Harmonic(N)-1或大约ln(N) - 0.4227843351.

快速检查一些简单的情况:

• N = 1,只有一个排列,没有最大更新.谐波(1) - 1 = 0.
• N = 2,排列为[1,2]和[2,1].第一次更新最大值,第二次更新零次,因此平均值为1/2.谐波(2) - 1 = 1/2.
• N = 3,排列为[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2] ,1].最大更新分别为2,1,1,1,0,0.平均值为(2 + 1 + 1 + 1)/ 6 = 5/6.谐波(3) - 1 = 1/2 + 1/3 = 5/6.

所以理论上的答案看起来不错!

Answer 2

经验解

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

#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
• 下一个最大值将是 m+1...n 范围内的随机数，其平均值为 (m+n)/2
• 这意味着每次找到新的最大值时，您都会将可能的最大值范围除以 2
• 重复除法相当于对数
• 因此，找到新最大值的次数为O(log n)