Что такое значение O для наивного случайного выбора от конечного множества?

Если вы хотите сделать предположение, что ваш генератор случайных чисел всегда будет находить уникальное значение перед циклическим возвратом к ранее обнаруженному значению для данного розыгрыша, этот алгоритм - O (m ^ 2), где m - количество уникальных значений, которые вы рисуете.

Итак, если вы рисуете m значений из набора n значений, первое значение потребует от вас нарисовать не более 1, чтобы получить уникальное значение. Для второго требуется не более 2 (вы видите 1-е значение, затем уникальное значение), для 3-го 3, ... m-го m. Следовательно, всего вам потребуется 1 + 2 + 3 + ... + m = [m * (m + 1)] / 2 = (m ^ 2 + m) / 2 розыгрыша. Это O (m ^ 2).

Без этого предположения I ' Я не уверен, как можно гарантировать, что алгоритм завершится. Вполне возможно (особенно с генератором псевдослучайных чисел, который может иметь цикл), что вы будете продолжать видеть одни и те же значения снова и снова и никогда не перейдете к другому уникальному значению.

== EDIT ==

Для среднего случая:

В вашем первом розыгрыше вы сделаете ровно 1 розыгрыш. Во втором розыгрыше вы ожидаете получить 1 (успешный розыгрыш) + 1 / n («частичный» розыгрыш, который представляет ваш шанс на повторение розыгрыша). На третьем розыгрыше вы ожидаете получить 1 (успешный розыгрыш) + 2 / n («частичный» розыгрыш ...) ... На m-м розыгрыше вы ожидаете сделать 1 + (m-1) / n розыгрышей.

Таким образом, вы получите 1 + (1 + 1 / n) + (1 + 2 / n) + ... + (1 + (m-1) / n) полностью вытягивается в среднем случае.

Это равно сумме от i = 0 до (m-1) из [1 + i / n]. Обозначим эту сумму (1 + i / n, i, 0, m-1).

Затем:

sum(1 + i/n, i, 0, m-1) = sum(1, i, 0, m-1) + sum(i/n, i, 0, m-1)
                        = m + sum(i/n, i, 0, m-1)
                        = m + (1/n) * sum(i, i, 0, m-1)
                        = m + (1/n)*[(m-1)*m]/2
                        = (m^2)/(2n) - (m)/(2n) + m 

Мы отбрасываем члены младшего порядка и константы и получаем, что это O (m ^ 2 / n), где m - число, которое нужно нарисовать, а n - размер списка.

Если вы уже выбрали i значений, то вероятность того, что вы выберете новое из набора значений y, будет

 (yi) / y.

Следовательно, ожидаемое количество попыток получить (i + 1) -й элемент равно

 y / (yi).

Таким образом, ожидаемое количество попыток выбора уникального элемента x равно сумме

  y / y + y / (y-1) + ... + y / (y-x + 1)

Это можно выразить с помощью чисел гармоник как

y (H _y - H _yx ).

На странице википедии вы получите приближение

H _x = ln (x) + gamma + O (1 / x)

Следовательно, количество необходимых испытаний для выбора x уникальных элементов из набора y элементов равно

 y (ln (y) - ln (yx)) + O (y / (yx)).

Если вам нужно, вы можете получить более точное приближение, используя более точное приближение для H _x . В частности, когда x мало, можно значительно улучшить результат.

Для этого есть прекрасный алгоритм O (n). Это происходит следующим образом. Допустим, у вас есть n предметов, из которых вы хотите выбрать m. Я предполагаю, что функция rand () дает случайное вещественное число от 0 до 1. Вот алгоритм:

items_left=n
items_left_to_pick=m
for j=1,...,n
    if rand()<=(items_left_to_pick/items_left)
        Pick item j
        items_left_to_pick=items_left_to_pick-1
    end
    items_left=items_left-1
end

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

Edit Преимущество этого алгоритма в том, что он занимает только O (m) памяти (при условии, что элементы являются просто целыми числами или могут быть созданы на -fly) по сравнению с перемешиванием, которое требует O (n) памяти.

Ваш настоящий вопрос на самом деле намного интереснее, чем то, на что я ответил (и сложнее). Я никогда не был хорош в статистике (и уже давно не занимался этим), но интуитивно я бы сказал, что сложность времени выполнения этого алгоритма, вероятно, будет чем-то вроде экспоненциальной. Пока количество выбранных элементов достаточно мало по сравнению с размером массива, частота столкновений будет настолько мала, что будет близка к линейному времени, но в какой-то момент количество столкновений, вероятно, будет быстро расти, и выполнение -время пойдет насмарку.

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

РЕДАКТИРОВАТЬ: Подумав, вот моя попытка:

Учитывая массив из m элементов и ищу n случайных и разных элементов. Тогда легко увидеть, что когда мы хотим выбрать i -й элемент, шансы выбрать элемент, который мы уже посетили, составляют (i-1) / m . Тогда это ожидаемое количество столкновений для данного выбора. Для выбора n элементов ожидаемое количество столкновений будет суммой количества ожидаемых столкновений для каждого выбора. Мы вставляем это в Wolfram Alpha (сумма (i-1) / m, i = от 1 до n), и получаем ответ (n ** 2 - n) / 2m .

Прежде чем мы сможем подробно ответить на этот вопрос, давайте определим структуру. Предположим, у вас есть коллекция {a1, a2, ..., an} из n различных объектов, и вы хотите выбрать m различных объектов из этого набора, так что вероятность появления данного объекта aj в результате одинакова для всех объектов. .

Если вы уже выбрали k предметов и быстро выбрали предмет из полного набора {a1, a2, ..., an}, вероятность того, что этот предмет не был выбран раньше, равна (nk) / n. Это означает, что количество выборок, которые вам нужно сделать, прежде чем вы получите новый объект, составляет (при условии независимости от случайной выборки) геометрическое с параметром (nk) / n. Таким образом, ожидаемое количество выборок для получения одного дополнительного элемента равно n / (nk), что близко к 1, если k мало по сравнению с n.

В заключение, если вам нужно m уникальных объектов, * Ожидаемое количество образцов для получения нового уникального элемента увеличивается с увеличением количества уже выбранных объектов (что звучит логично). * Вы можете ожидать действительно длительного времени вычислений, когда m близко к n, особенно если n велико.

Чтобы получить m уникальных элементов из набора, используйте вариант алгоритма Дэвида Кнута для получения случайная перестановка. Здесь я предполагаю, что n объектов хранятся в массиве.

for i = 1..m
  k = randInt(i, n)
  exchange(i, k)
end

здесь randInt выбирает целое число из {i, i + 1, ... n}, а exchange переворачивает два члена массива. Вам нужно перетасовать только m раз, поэтому время вычисления равно O (m), тогда как память - O (n) (хотя вы можете адаптировать его для сохранения только записей, таких что a [i] <> i, что даст you O (m) как по времени, так и по памяти, но с более высокими константами).

Очевидно, что наихудший случай для этого алгоритма - это когда вы выбираете полный набор из N элементов. Это эквивалентно вопросу: в среднем, сколько раз я должен бросить N-сторонний кубик, прежде чем каждая сторона выпадет хотя бы один раз?

Ответ: N * H _N , где H _{] N} - номер N-й гармоники ,

значение, известное приближение log (N) .

Это означает, что рассматриваемый алгоритм - N log N .

В качестве забавного примера, если вы бросите обычный 6-гранный кубик, пока не увидите одно из каждого числа, это займет в среднем 6 H ₆ = 14,7 бросков.

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

Количество необходимых попыток, как описано ранее, можно оценить по формуле

T(n,m) = n(H(n)-H(n-m)) ⪅ n(ln(n)-ln(n-m))

, которая переходит в n * ln (n) для интересных значений m

Однако для при каждой из этих «попыток» вам придется выполнять поиск. Это может быть простой просмотр O (n) или что-то вроде двоичного дерева. Это даст вам общую производительность n ^ 2 * ln (n) или n * ln (n) ^ 2 .

Для меньших значений m ( m ), вы можете сделать очень хорошее приближение для T (n, m) , используя HA -уравнение, дающее формулу:

2*m*n/(2*n-m+1)