Eu quero escolherk elementos uniformemente aleatoriamente fora de um possíveln sem escolher o mesmo número duas vezes. Existem duas abordagens triviais para isso.

Faça uma lista de todosn possibilidades. Embaralhe-os (você não precisa embaralhar tudon números apenask deles, realizando o primeirok etapas de Fisher Yates). Escolha o primeirok. Essa abordagem levaO(k) tempo (assumindo a alocação de uma matriz de tamanhon levaO(1) tempo eO(n) espaço. Este é um problema sek é muito pequeno em relação an.Armazene um conjunto de elementos vistos. Escolha um número aleatoriamente entre[0, n-1]. Enquanto o elemento estiver no conjunto, escolha um novo número. Essa abordagem levaO(k) espaço. O tempo de execução é um pouco mais complicado de analisar. E sek = theta(n) então o tempo de execução éO(k*lg(k))=O(n*lg(n)) porque é oproblema do colecionador de cupons. E sek é pequeno em relação an então é preciso um pouco mais do queO(k) por causa da probabilidade (embora baixa) de escolher o mesmo número duas vezes. Isso é melhor que a solução acima em termos de espaço, mas pior em termos de tempo de execução.

Minha pergunta:

existe umO(k) Tempo,O(k) algoritmo espacial para todosk en?