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

Ответ 1

Переменные

n= общее количество элементов в наборе
m= количество уникальных значений, которые должны быть получены из набора n элементов
d (i)= ожидаемое количество попыток, необходимых для достижения значения на шаге я
i= denotes one specific step. я ∈ [0, n-1]
T (m, n)= ожидаемое общее количество попыток выбора m уникальных элементов из набора из n элементов с использованием наивного алгоритма

Рассуждение

Первый шаг, я = 0, тривиален. Независимо от того, какое значение мы выберем, мы получим уникальный с первой попытки. Следовательно:

d (0) = 1

На втором шаге я = 1 нам потребуется хотя бы одна попытка (попробуйте, где мы выберем действительное уникальное значение). Кроме того, есть шанс, что мы выберем неправильное значение. Этот шанс (количество ранее выбранных предметов)/(общее количество предметов). В этом случае 1/n. В случае, когда мы выбрали неправильный элемент, есть шанс 1/n, мы можем снова выбрать неправильный элемент. Умножая это на 1/n, так как это комбинированная вероятность того, что мы выбираем неправильное оба раза, дает (1/n) ². Чтобы понять это, полезно нарисовать дерево решений . Выбрав не уникальный элемент дважды, есть вероятность, что мы сделаем это снова. Это приводит к добавлению (1/n) ³ к общим ожидаемым количествам попыток на этапе я = 1. Каждый раз, когда мы выбираем неправильный номер, есть шанс, что мы снова заберем неправильный номер. Это приводит к:

d (1) = 1 + 1/n + (1/n) ² + (1/n) ³ + (1/n) ⁴ +...

Аналогично, на общем i-м шаге, возможность выбрать неправильный элемент в одном выборе - это i/n, в результате чего:

d(i) = 1 + i/n + (i/n) ² + (i/n) ³ + (i/n) ⁴ +... =
= sum( (i/n) ^k), where k ∈ [0,∞]

Это геометрическая последовательность и, следовательно, легко вычислить ее сумму:

d (i) = (1 - i/n) ^-1

Общая сложность вычисляется суммированием ожидаемого количества попыток на каждом шаге:

T(m,n) = sum ( d(i)), where я ∈ [0,m-1] =
= 1 + (1 - 1/n) ^-1 + (1 - 2/n) ^-1 + (1 - 3/n) ^-1 +... + (1 - (m-1)/n) ^-1

Расширяя дроби в следующем порядке на n, получим:

T (m, n) = n/n + n/(n-1) + n/(n-2) + n/(n-3) +... + n/(n-m + 2 ) + n/(n-m + 1)

Мы можем использовать тот факт, что:

n/n ≤ n/(n-1) ≤ n/(n-2) ≤ n/(n-3) ≤... ≤ n/(n-m+2) ≤ n/(n-m+1)

Так как ряд имеет m слагаемых, и каждый член удовлетворяет вышеприведенному неравенству, получаем:

T(m,n) ≤ n/(n-m+1) + n/(n-m+1) + n/(n-m+1) + n/(n-m+1) +... + n/(n-m+1) + n/(n-m+1) =
= m*n/(n-m+1)

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

Заключение

Это означало бы, что порядок Big-O O (m * n/(n-m + 1)). Я не вижу возможности упростить это выражение так, как оно есть.

Looking back at the result to check if it makes sense, we see that, if n is constant, and m gets closer and closer to n, the results will quickly increase, since the denominator gets very small. This is what we'd expect, if we for example consider the example given in the question about selecting "999,999 values from a set of 1,000,000". If we instead let m be constant and n grow really, really large, the complexity will converge towards O(m) in the limit n → ∞. This is also what we'd expect, since while chosing a constant number of items from a "close to" infinitely sized set the probability of choosing a previously chosen value is basically 0. I.e. We need m tries independently of n since there are no collisions.

Ответ 2

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

(y-i)/y.

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

y/(y-i).

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

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

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

y (H _y - H _y-x).

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

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

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

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

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

Ответ 3

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

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

РЕДАКТИРОВАТЬ: после некоторого раздумья, здесь моя попытка:

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

Если моя память не полностью сработает (что вполне возможно, на самом деле), это дает время выполнения среднего времени O(n**2).

Ответ 4

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

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

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

== == EDIT

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

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

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

Это равно сумме от я = 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 - размер списка.

Ответ 5

Для этого существует красивый алгоритм 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 элементов с равной вероятностью, хотя доказательство неочевидно. К сожалению, на данный момент у меня нет ссылки.

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

Заканчивая, если вам нужно m уникальных объектов, случайно выбранных, этот алгоритм дает вам

n/n + n/(n-1) + n/(n-2) + n/(n-3) +.... + n/(n- (m-1))

который, как показал Алдерат, можно оценить с помощью

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

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

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

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

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

Ответ 8

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

Количество попыток nessesary может, как описано ранее, оцениваться по:

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 < n/2) вы можете сделать очень хорошее приближение для T(n,m), используя HA -единение, получив формулу:

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

Поскольку m переходит в n, это дает нижнюю границу попыток и производительности O(n) и производительности O(n^2) или O(n*ln(n)).

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