Можно ли генерировать разные случайные числа быстрее, чем O (n)?

Question

У меня есть диапазон чисел от 1 до 10, и я хочу выбрать 3 случайно, но никогда не повторяясь дважды.В lua я использовал случайную запись Фишера-Йейтса O (n), я знаю, что в python есть встроенная функция random.sample () и O (n).Можно ли сделать это быстрее с произвольным диапазоном и количеством пиков?

Answer 1

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

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