Сколько раз переменная m обновляется

Question

Учитывая следующий псевдокод, вопрос в том, сколько раз в среднем обновляется переменная m .

A[1...n]: array with n random elements 
m = a[1]
for I = 2 to n do
   if a[I] < m then m = a[I]
end for

Кто-то может ответить, что, поскольку все элементы случайны, переменная будет обновляться в среднем на половину числа итераций цикла for плюс один для инициализации.

Однако я подозреваю, что должен быть лучший (и, возможно, единственный правильный) способ доказать это с помощью биномиального распределения с p = 1/2 . Таким образом, среднее количество обновлений на m будет

M = 1 + Σi=1 to n-1[k.C<sub>n,k</sub>.p<sup>k</sup>.(1-p)<sup>(n-k)</sup>]

, где C _{n, k} - биномиальный коэффициент. Я пытался решить эту проблему, но я застрял несколько шагов после, так как я не знаю, как продолжить.

Может ли кто-нибудь объяснить мне, какой из двух ответов является правильным, и если это второй, показать мне, как рассчитать M ?

Спасибо за ваше время

Answer 1

Мне понравился @ rici ответ, поэтому я решил немного подробнее развить его центральный аргумент, чтобы он был понятнее для меня.

Пусть H[k] будет ожидаемым числом назначений, необходимых для вычисления минимальной m массива длины k, как указано в рассматриваемом алгоритме. Мы знаем, что

H[1] = 1.

Теперь предположим, что у нас есть массив длины n > 1. Мин может быть в последней позиции массива или нет. Это в последней позиции с вероятностью 1/n. Это не с вероятностью 1 - 1/n. В первом случае ожидаемое количество назначений составляет H[n-1] + 1. Во втором H[n-1].

Если мы умножим ожидаемое количество назначений каждого случая на их вероятности и сумму, мы получим

H[n] = (H[n-1] + 1)*1/n + H[n-1]*(1 - 1/n)
     = H[n-1]*1/n + 1/n + H[n-1] - H[n-1]*1/n
     = 1/n + H[n-1]

, который показывает рекурсию.

Обратите внимание, что аргумент действителен, если min находится либо в последней позиции, либо в любой первой n-1, а не в обоих местах. Таким образом, мы используем, чтобы все элементы массива были разными.

Answer 2

Предполагая, что элементы массива различны, ожидаемое количество обновлений m представляет собой n ^th номер гармоники , H _n , который сумма 1 / k для k в диапазоне от 1 до n.

Формула суммирования также может быть представлена ​​рекурсией:

H<sub>1</sub> &equals; 1
H<sub>n</sub> &equals; H<sub>n&minus;1</sub>&plus;1/n (n > 1)

Легко видеть, что рекурсия соответствует проблеме.

Рассмотрим все перестановки чисел n & min; 1 и предположим, что ожидаемое количество назначений H _{n & min; 1} . Теперь каждая перестановка из n чисел состоит из перестановки из чисел n & минус 1, с новым наименьшим числом, вставленным в одну из n возможных точек вставки: либо в начале, либо после одного из n & минус 1 существующих значений. Поскольку он меньше, чем каждый номер в существующей серии, он будет назначен только в том случае, если он был вставлен в начале. Это имеет вероятность 1 / n, и поэтому ожидаемое количество назначений перестановки из n чисел составляет H _{n & minus; 1} + 1 / n.

Поскольку ожидаемое число назначений для вектора длины один, очевидно, равно 1, что равно H ₁ , у нас есть индуктивное доказательство рекурсии.

H _n асимптотически равно ln n & plus; &гамма; где & гамма; составляет постоянная Эйлера-Маскерони , приблизительно 0,577. Так что он увеличивается без ограничений, но довольно медленно.

Значения, для которых обновляется m, называются максимумы слева направо , и вы, вероятно, найдете больше информации о них, выполнив поиск по этому термину.