К содержанию
Quantoros

Просматриваем n различных чисел в случайном порядке. Записываем новый максимум, включая первый элемент. Сколько…

Quant ResearchУровень: ПрактикаRecords in a random order

Просматриваем n различных чисел в случайном порядке. Записываем новый максимум, включая первый элемент. Сколько записей в среднем?

Подсказки
  • Максимум первых k равновероятен в каждой позиции.
  • Для сложения ожиданий независимость не нужна.

Ответ

k-й элемент максимален среди первых k с вероятностью 1/k. Ожидание H_n=Σ1/k≈log n+γ. Если не считать инициализацию, ответ H_n-1.

Источник и лицензия: Lehman, Leighton & Meyer — Mathematics for Computer Science (2018-06-06) · CC-BY-SA-3.0 · ответ: редакция Quantoros · перевод: Quantoros

Похожие вопросы