Encontre min comum em tempo logarítmico

Eu estou procurando por uma estrutura de dados para armazenar um conjunto que, considerando duas instâncias do tamanho que são conhecidas por terem interseção não vazia, o elemento mínimo da interseção possa ser encontrado em . Isso é possível de alcançar, para o pior caso ou para a complexidade amortizada? Outros requisitos para a estrutura de dados: deleção, a inicialização. $O(n)$ $O(\log n)$ $O(\log n)$ $O(n \log n)$

Aqui está um exemplo de aplicação dessa estrutura de dados, para esclarecer os requisitos. A entrada consiste em n subconjuntos de todos contendo o número n. A saída é uma matriz n por n cuja entrada é o elemento mínimo na interseção dos conjuntos iej. Com uma abordagem básica, pode-se resolver esse problema em . Com uma estrutura de dados que satisfaça as condições acima, pode-se resolvê-la em . $\{1, ..., n\}$ $i, j$ $O(n^3)$ $O(n^2 \log n)$

data-structures heaps pré-rim
fonte

A situação em que estou mais interessado é quando os conjuntos têm cauda inferior esparsa, com a densidade aumentando constantemente. Por exemplo, existe um algoritmo O (d log n) óbvio para conjuntos com densidade limitada abaixo de 1 / d, em que você usa min heaps e começa no mínimo de um conjunto e, em seguida, executa ping-pong sempre pegando o próximo maior elemento na pilha até você estabilizar.

pré-rim

O que significa para um conjunto ter uma cauda inferior esparsa ou para aumentar sua densidade constantemente?

Por exemplo, pensar de um conjunto aleatório onde elemento i é incluído com probabilidade 1 / (ni) para i <n e n é incluído com probabilidade 1.

pré-renal

Se você conseguir editar a pergunta para especificar um problema específico. distribuição, que pode facilitar a solução. Por exemplo, se cada conjunto for escolhido aleatoriamente (onde o elemento i é incluído com probabilidade p, independentemente de i), acho que existe um algoritmo natural cujo tempo de execução esperado é algo como : primeiro enumere todos os pares de conjuntos que ambos contêm 1; todos os pares que contêm 1 (mas ainda não foram encontrados); e assim por diante. Existe uma condição de parada simples e, se os conjuntos forem aleatórios, você não precisará continuar muito antes de parar.

O (n^{2} \log n)

$O(n^2 \log n)$

S_{i}, S_{j}

$S_i,S_j$

Como outro exemplo, para a distribuição específica em seu comentário, existe um algoritmo simples de tempo , pois o tamanho esperado de cada conjunto é .

O (n^{2} \log n)

$O(n^2 \log n)$

O (\log n)

$O(\log n)$

Respostas:

Você não pode. Não existe essa estrutura de dados. Supondo que você tenha uma instância separada por conjunto e cada instância seja inicializada separadamente (usando apenas informações sobre o conjunto que representa e não informações sobre nenhum dos outros conjuntos), esses tempos de execução não são alcançáveis.

Em particular, quando você tem dois conjuntos, encontrar o elemento comum mínimo leva . De fato, testar a disjunção requer tempo , conforme explicado aqui . Agora, imagine começar com dois conjuntos sobre o universo . Deixe e . Agora são garantidos para ter um elemento comum. Portanto, se você tiver uma boa estrutura de dados para o seu problema, armazene em uma instância da estrutura de dados e em outra. Então, se tivéssemos uma maneira de encontrar o elemento mínimo de em $\Omega(n)$ $\Omega(n)$ $S_1,S_2$ $\{1,2,\dots,n-1\}$ $T_1=S_1 \cup \{n\}$ $T_2 = S_2 \cup \{n\}$ $T_1,T_2$ $T_1$ $T_2$ $T_1 \cap T_2$ $o(n)$ tempo, isso nos daria uma maneira de testar a de em tempo (apenas teste se o elemento mínimo é menor que ) - mas já sabemos que o último não é possível. Daqui resulta que o primeiro também não é possível, ou seja, qualquer estrutura de dados para o seu problema deve levar para encontrar o elemento comum mínimo de dois conjuntos. $S_1,S_2$ $o(n)$ $n$ $\Omega(n)$

Isso não significa que seu aplicativo não possa ser resolvido com eficiência. Ainda pode haver uma maneira de resolver seu aplicativo em ; esse resultado não descarta isso. $O(n^2 \log n)$

DW
fonte

Eu gostaria muito que você pudesse tornar sua resposta um pouco mais independente, pois ela cita sua resposta em outro post que, por sua vez, cita um resultado ao qual você não mencionou.

pré-rim

Deixe-me apontar exatamente qual etapa, acredito, precisa de mais elaboração. A etapa principal do seu argumento é a afirmação de que, para conjuntos armazenados de qualquer maneira, mas incapazes de acessar a memória um do outro, resolver o problema de decisão de desarticulação leva tempo Omega (n). Você afirma que qualquer algoritmo mais rápido contradiz os resultados básicos da complexidade da comunicação. No entanto, esse modelo do canal de comunicação parece ser mais geral do que os modelos básicos de comunicação que encontrei na literatura, pelos quais o limite Omega (n) é conhecido. É por isso que peço uma citação específica.

pré-rim

@ pré-rim, eu não entendo como isso parece mais geral. De qualquer forma, parece que sua objeção é primariamente a minha outra resposta , então vamos discutir qualquer assunto por favor. Eu editei minha resposta lá para articular a redução em detalhes. Se você tiver uma preocupação específica sobre o modelo de computação, comente aqui explicando especificamente que diferença de modelo de computação você vê. Não vejo uma, mas isso não significa que você esteja errado - não sou especialista nesse assunto e sempre posso estar enganado.

Pontos justos e obrigado pela atualização. Vai dar uma olhada.

pré-rim

-1

Aqui está uma idéia para resolver o problema, com dois conjuntos:

Você pode segurar "conjuntos" por uma árvore vermelha e preta. Além disso, para cada nó da árvore, associamos um bit para determinar se sua subárvore contém um elemento nos dois conjuntos. Para fins de apresentação, é chamado de bit de inserção . Presumo que a árvore preta e vermelha classifique os elementos da esquerda para a direita.

Ao inserir um elemento na árvore, o algoritmo verifica se o elemento existe na árvore (ou seja, no outro conjunto). Caso contrário, inserimos o elemento como de costume. Caso contrário, viajando da raiz para a folha que contém o elemento, o algoritmo ativa o bit de inserção dos nós correspondentes. Na pior das hipóteses, é necessário . $O(\log n)$

Ao excluir um elemento, o algoritmo verifica se o elemento existe na árvore e se o bit de inserção está ativado. Se o elemento não existir na árvore, retornamos um erro. Se o elemento existir e o bit de inserção estiver desativado, excluiremos o elemento como no algoritmo da árvore Red Black. Caso contrário, viajando da raiz para a folha que contém o elemento, o algoritmo desativa o bit de inserção dos nós correspondentes. A exclusão leva . $O(\log n)$

Finalmente, o algoritmo para encontrar o elemento mínimo compartilhado pelos dois conjuntos começa com a raiz. Se o bit de inserção da raiz for desativado - os conjuntos serão desarticulados, o algoritmo retornará um erro. Caso contrário, o algoritmo viaja recursivamente para o filho esquerdo se seu bit de inserção estiver ativado e, caso contrário, ele viaja para o filho certo. O algoritmo para no elemento com o valor mínimo. O algoritmo é executado em . $O(\log n)$

Estou tentando pensar em como generalizar o para um número maior de conjuntos ...

user3563894
fonte

Isso não atende aos critérios estabelecidos, uma vez que assume que as duas instâncias são conhecidas uma da outra durante a inicialização - se você tivesse muitas instâncias e precisasse encontrar interseções mínimas em pares, isso não atenderia ao tempo, pois seria necessário reconstruir a estrutura de dados para cada par de conjuntos.

pré-rim

Se as instâncias não se conhecerem, você poderá mesclá-las em tempo usando en.wikipedia.org/wiki/…

O (n)

$O(n)$

Qual é a entrada do problema? Ao inicializar os conjuntos você pode inserir \ eliminar os elementos em uma árvore comum, e em seguida, usando operações sucessivas de exclusão e inserção não afetará a complexidade de uma consulta, que leva

O (\log n)

$O(\log n)$

user3563894

Esse é o ponto, os conjuntos não podem ser acoplados. Deixe-me atualizar minha pergunta com um exemplo de aplicação dessa estrutura de dados, para esclarecer.

pré-rim

A propósito, eu não votei em desacordo com você - acho que sua resposta é útil para a discussão e esclarecimentos extras que ela gerou, mesmo que ela não responda de verdade à minha pergunta.

pré-rim

-1

Inicialize:
1) crie uma árvore vermelho-preta contendo todos os elementos da lista 1 - O (n log n) para toda a lista.
2) repita todos os elementos da lista nº 2 e verifique se ela existe na árvore vermelha e preta - O (n log n) para toda a lista
3) se ela existe na árvore vermelha e preta, insira esse elemento da lista # 2 na sua pilha mínima favorita - O (n log n) para toda a lista

Para pesquisar, encontre o elemento mínimo de interseção, basta olhar para o topo da pilha, então é O (1).

Churro
fonte

Essa abordagem sofre dos mesmos problemas da resposta do usuário3563894, consulte os comentários lá.

pré-rim