Блог пользователя vitux

Очень интересная и увлекательная задача
Автор vitux, 10 лет назад, По-русски

Есть вот такая вот функция. 

def test(k):
	i = 0
	j = randint(0, k - 1) # randint(0, k - 1) - случайное целое число из [0, k - 1]
	while i < j:
		i += 1
		j = randint(0, k - 1)
	return i

Какое математическое ожидание величины test(k)? Требуется посчитать быстрее, чем за O(k).

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ответ порядка sqrt(k), так что можно посчитать за O(ответа). Просто считаем по очереди p_i = вероятность того, что будет возвращено число i. Эта величина легко пересчитывается (p_(i+1) = (1 — p_i) * (i + 1) / k, если считать p_0 = 0 и что числа генерируются от 1 до k, а не от 0 до k-1).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Это за O(k), а можно ли быстрее? Может можно как-то ряд просуммировать

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      Почему O(k)? O(sqrt(k)). Нам не нужны все значения p_i, а лишь p_i с i<5sqrt(k), Может, и можно.

      → Ответить