5

我有一个算法，它将一个数组作为参数，并返回它的最大值。

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]，则更新次数为max1（读取值 3 时）。

4

3 回答 3

7

假设原始数组包含值 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)，即 prob(1 出现为最大值) + prob(2 出现为最大值) + ... + prob （N 显示为最大值）（因为每个 X_i 取值 0 或 1）。

我什么时候出现最大值？它是当它首先出现在 i、i+1、i+2、...、N 中的数组中时。这种概率是 1/(N-i+1)（因为这些数字中的每一个都同样可能成为第一）。

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

这是谐波（N），它由 ln(N) + emc 非常近似，其中 emc ~= 0.5772156649，欧拉-马斯切罗尼常数。

由于在问题中您没有将最大值的初始设置计为第一个值，因此实际答案是谐波（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。

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

于 2013-09-29T08:19:01.080 回答
4

经验解

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

#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)
于 2013-09-29T07:12:33.657 回答
0

最坏的情况（通常是寻求的）是 O(n)。如果列表以相反的顺序排序，则每一个都会导致分配。

但是，如果您的分配是最昂贵的操作，为什么不只存储它的索引并且只复制一次，如果有的话？在这种情况下，您将有 1 个分配和 n-1 个比较。

于 2013-09-30T23:08:31.063 回答