Этот вопрос получение случайных значений из конечного множества заставило меня задуматься ...

Люди довольно часто хотят получить X уникальных значений из набора значений Y. Например, я могу захотеть разыграть руку из колоды карт. Я хочу 5 карт, и я хочу, чтобы они были уникальными.

Теперь я могу сделать это наивно, выбрав случайную карту 5 раз и повторять каждый раз, когда получаю дубликат, пока не получу 5 карт. Это не так здорово, однако, для большого количества значений из больших наборов. Например, если мне нужно 999 999 значений из набора 1 000 000, этот метод очень плохой.

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

(Вопрос не в том, «как я могу улучшить это?», Потому что это относительно легко исправить, и я уверен, что это было рассмотрено много раз в других местах.)