Considere um vetor dimensional v em que v i ∈ { 0 , 1 } . Para cada i sabemos p i = P ( v i = 1 ) e vamos assumir o v i são independentes. Usando essas probabilidades, existe uma maneira eficiente de iterar sobre vetores binários n dimensionais, na ordem do mais provável para o menos provável (com opções arbitrárias de vínculos) usando o espaço sublinear no tamanho da saída?
Tomemos, por exemplo, . O vetor mais provável é ( 1 , 0 , 1 ) e o menos provável é { 0 , 1 , 0 } .
Para muito pequeno , poderíamos rotular cada um dos 2 n vetores com sua probabilidade e simplesmente classificar, mas isso obviamente ainda não usaria espaço sublinear.
Uma variante aproximada dessa pergunta foi feita anteriormente em /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .
fonte
Respostas:
A seguir, é apresentado um algoritmo que usa aproximadamente tempo e 2 n / 2 de espaço.2n 2n / 2
Primeiro, vejamos o problema de classificar as somas de todos os subconjuntos de itens.n
Considere este subproblema: você tem duas listas classificadas de comprimento e gostaria de criar uma lista classificada das somas aos pares dos números nas listas. Você gostaria de fazer isso em aproximadamente O ( m 2 ) tempo (o tamanho da saída), mas em espaço sublinear. Podemos alcançar O ( m ) espaço. Mantemos uma fila de prioridade e extraímos as somas da fila de prioridade em ordem crescente.m O ( m2) O ( m )
Deixe as listas de ser e b 1 ... b m , classificados em ordem crescente. Tomamos as m somas a i + buma1... am b1... bm m , i = 1 ... m , e colocá-los em uma fila de prioridade.umaEu+ b1 i = 1 … m
Agora, quando extraímos a menor soma restante da fila de prioridade, se j < m , então colocamos a soma a i + b j + 1 na fila de prioridade. O espaço é dominado pela fila de prioridade, que contém sempre a maioria m somas. E o tempo é O ( m 2 log m ) , já que usamos O ( log mumaEu+ bj j < m umaEu+ bj + 1 m O ( m2registrom ) para cada operação na fila de prioridade. Isso mostra que podemos fazer o subproblema em O ( m 2O ( logm ) tempo e O ( m ) espaço.O ( m2registrom ) O ( m )
Agora, para classificar as somas de todos os subconjuntos de números, usamos apenas esta sub-rotina em que a listan é o conjunto de somas de subconjuntos da primeira metade dos itens, ea lista b i é o conjunto de somas de subconjuntos da segunda metade dos itens. Podemos encontrar essas listas recursivamente com o mesmo algoritmo.umaEu bEu
Vamos agora considerar o problema original. Seja o conjunto de coordenadas 0 e S 1 o conjunto de coordenadas 1 . Então Π i ∈ S 0 p ( v i = 0 ) Π i ∈ S 1S0 0 0 0 S1 1
Classificar esses números é o mesmo que classificar os números , de modo que têm reduzido o problema para classificar os somas de subconjuntos de n itens.∑i∈S1logp(vi=1)−logp(vi=0) n
fonte
Podemos fazer isso no espaçoO(n)
(Também devemos cuidar de possíveis laços, mas isso não é difícil.)
fonte
Editar: esta resposta está incorreta. Veja os comentários para obter detalhes. ~ gandaliter
Chame essa função recursiva na lista classificada e um vetor vazio.
fonte