Ожидаемое количество заданий, чтобы найти максимальное значение в массиве

Question

В следующем коде Java:

int max = arr[0]; 
for (int i = 0; i < arr.length i++) { 
    if (arr[i] > max) { 
     max = arr[i]; 
    } 
} 

Сколько раз делает линию max = arr[i]; пробег, предполагая, что массив несортированный.

Answer 1

Ожидаемые оценки могут быть вычислены по линейности ожиданий. Я мог бы дать более строгий ответ, если этот сайт поддерживает MathJax.

Ответ представляет собой сумму 1/(n-i + 1) для i = 1 до n = сумма 1/i для i = 1 до n = O (log n), где n - размер массива (при условии, что все элементы массива различны)

Предупреждение, Math-sy part ahead.

Основная идея состоит в том, что если мы назначим каждому элементу лексикографический индекс «i», где «i» означает, что этот элемент является наименьшим элементом «i», тогда присваивание произойдет только в том случае, если ни один из n-i +1 больше элементов apprar до i-го элемента массива. Вероятность того, что это происходит в случайном массиве, равна 1/(n-i + 1) для всех i. Затем мы просто применяем линейность ожиданий с использованием индикаторной случайной величины: