尝试在随机数字数组中查找运行最大值时，需要调用多少次更新最大值？ [英] How many times update maximum gets called when trying to find the running maximum in a randomized array of numbers?

问题描述

假设我们有一个数组，其数组大小为-N到N，其数组大小为2N +1。我们首先对数组中的元素进行混洗，然后尝试通过从第一个元素到数组的迭代遍历数组来找到最大整数。最后一个元素：（代码示例在Java中）

Suppose we have an array with integers -N to N in an array size of 2N + 1. We first shuffle the elements in the array, then try to find the maximum integer by iterating through the array from the first element to the last element: (code example is in Java)

int called = 0;
int max = Integer.MIN_VALUE;
for (int i : array) {
    if (i > max) {
        called++;
        max = i;
    }
}

对什么的期望（多次运行的平均值）遍历数组后的值称为？

What is the expectation(average over many runs) of value called after iterating through the array?

编辑：

我如何发现它接近ln（array.length）：

How I found it to be close to ln(array.length):

public static void main(String args[]) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) list.add(i);

    int called = 0;
    int runs = 100;

    for (int i = 1; i <= runs; i++) {
        Collections.shuffle(list);
        int max = -1;
        for (int num : list) {
            if (num > max) {
                called++;
                max = num;
            }
        }
    }
    System.out.println("Expectation: " + called/runs);
}

推荐答案

让我们考虑一下随机重组的数组。我们要估计K-比第i个元素要大得多的次数。

Let's consider randomly shuffled array. We want to estimate K - number of times than i-th element is bigger than all of its predecessors.

K的期望值等于第i个元素的概率之和element比其所有前任更大。 E（K）=Σ ₁ ^{2N + 1} P _i 。

Expected value of K equals to sum of probabilities that i-th element is bigger than all its predecessors. E(K) = Σ₁^2N+1 P_i.

现在我们要找到P _i 。考虑数组的长度为i的前缀。前缀中的最后一个元素最大的概率为1 / i。因此我们有P _i = 1 / i。

Now we want to find P_i. Consider prefix of length i for our array. Probability that the last element in the prefix is the biggest is 1/i. So we have P_i = 1/i.

因此：E（K）=Σ ₁ < sup> 2N + 1 1 / i。我们可以通过定积分来估计总和为ln（2N + 1）+ O（1）。

Consequently:E(K) = Σ₁^2N+11/i. We can estimate this sum via definite integral as ln(2N+1)+O(1).

和蒙特卡洛模拟以求证明：

And Monte-Carlo simulation for kinda proof:

constexpr size_t N = 1000;
std::array<int, 2 * N + 1> arr;
std::iota(arr.begin(), arr.end(), -N);
std::random_device rd;
std::mt19937 g(rd());
double moving = 0;
for (double trial = 1; trial < 10001; ++trial) {
    std::shuffle(arr.begin(), arr.end(), g);
    int called = 0;
    int max = std::numeric_limits<int>::min();
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > max) {
            ++called;
            max = arr[i];
        }
    }
    if (trial > 1) {
        moving = moving * ((trial - 1) / trial) + called / trial;
    }
    else {
        moving = called;
    }
}
cout << "actual:   " << moving << endl;
cout << "expected: " << std::log(2 * N + 1) << " + O(1)" << endl;

actual:   8.1581   
expected: 7.6014 + O(1)

这篇关于尝试在随机数字数组中查找运行最大值时，需要调用多少次更新最大值？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！