Um dos meus amigos recebeu essa pergunta da entrevista -
"Existe um fluxo constante de números vindo de uma lista infinita de números, dos quais você precisa manter uma estrutura de dados para retornar os 100 números mais altos em qualquer ponto do tempo. Suponha que todos os números sejam apenas números inteiros."
Isso é simples, você precisa manter uma lista classificada em ordem decrescente e acompanhar o número mais baixo da lista. Se o novo número obtido for maior que o número mais baixo, você deverá remover o número mais baixo e inserir o novo número na lista classificada, conforme necessário.
Então a pergunta foi estendida -
"Você pode garantir que o Pedido de inserção seja O (1)? É possível?"
Tanto quanto eu sabia, mesmo se você adicionar um novo número à lista e classificá-lo novamente usando qualquer algoritmo de classificação, seria melhor O (logn) para quicksort (eu acho). Então, meu amigo disse que não era possível. Mas ele não estava convencido, ele pediu para manter qualquer outra estrutura de dados em vez de uma lista.
Pensei em árvore binária balanceada, mas mesmo lá você não receberá a inserção na ordem de 1. Portanto, a mesma pergunta que eu tenho agora. Queria saber se existe alguma estrutura de dados que possa inserir na ordem de 1 para o problema acima ou não é possível.
Respostas:
Digamos que k é o número de números mais altos que você deseja conhecer (100 no seu exemplo). Em seguida, você pode adicionar um novo número no
O(k)
qual também estáO(1)
. PorqueO(k*g) = O(g) if k is not zero and constant
.fonte
N
o tamanho da lista classificada ou o número de itens que foram processados até agora? Se você processar 10000 itens e manter os 100 itens principais em uma lista ou processar 1000000000 itens e manter os 100 itens principais em uma lista classificada, os custos de inserção nessa lista permanecerão os mesmos.O(k*g) = O(g) if k not zero and constant
. =>O(50*1) = O(1)
.Mantenha a lista não classificada. Descobrir se um novo número deve ou não ser inserido levará mais tempo, mas a inserção será O (1).
fonte
Isso é facil. O tamanho da lista de constantes, portanto, o tempo de classificação da lista é constante. Uma operação que é executada em tempo constante é considerada O (1). Portanto, a classificação da lista é O (1) para uma lista de tamanho fixo.
fonte
Depois de passar 100 números, o custo máximo que você incorrerá para o próximo número é o custo para verificar se o número está nos 100 números mais altos (vamos rotular esse CheckTime ) mais o custo para inseri-lo nesse conjunto e ejetar o número o menor (vamos chamar de EnterTime ), que é tempo constante (pelo menos para números limitados) ou O (1) .
Em seguida, se a distribuição dos números for aleatória, o custo médio diminuirá quanto mais números você tiver. Por exemplo, a chance de você inserir o 101º número no conjunto máximo é 100/101, as chances para o 1000º número seriam 1/10 e as chances para o enésimo número seriam 100 / n. Assim, nossa equação para o custo médio será:
Assim, quando n se aproxima do infinito, apenas o CheckTime é importante:
Se os números estiverem vinculados, CheckTime é constante e, portanto, é hora O (1) .
Se os números não estiverem vinculados, o tempo de verificação aumentará com mais números. Teoricamente, isso ocorre porque se o menor número no conjunto máximo ficar grande o suficiente, o tempo de verificação será maior, pois você terá que considerar mais bits. Isso faz parecer que será um pouco maior que o tempo constante. No entanto, você também pode argumentar que a chance de o próximo número estar no conjunto mais alto se aproxima de zero quando n se aproxima do infinito e, portanto, a chance de você precisar considerar mais bits também se aproxima de 0, o que seria um argumento para O (1) Tempo.
Não sou positivo, mas meu intestino diz que é hora O (log (log (n))) . Isso ocorre porque a chance de o número mais baixo aumentar é logarítmica e a chance de que o número de bits que você precisa considerar para cada verificação também seja logarítmico. Estou interessado em outros povos, porque não tenho muita certeza ...
fonte
CheckTime + EnterTime
para cada número. Isto só faz sentido se os números são sem limites, e assimCheckTime
eEnterTime
será tanto aumento, pelo menos de forma logarítmica, devido ao aumento no tamanho dos números.este é fácil se você conhece árvores binárias de heap . Montes binários suportam a inserção em tempo constante médio, O (1). E você terá acesso fácil aos primeiros x elementos.
fonte
Se pela pergunta que o entrevistador realmente quis fazer "podemos garantir que cada número recebido seja processado em tempo constante", como muitos já apontaram (por exemplo, veja a resposta de @ duedl0r), a solução do seu amigo já é O (1) e seria assim mesmo se ele tivesse usado lista não classificada, ou tipo bolha, ou qualquer outra coisa. Nesse caso, a pergunta não faz muito sentido, a menos que seja uma pergunta complicada ou você se lembre errado.
Suponho que a pergunta do entrevistador foi significativa, que ele não estava perguntando como fazer algo para ser O (1), o que já é muito óbvio.
Como a complexidade do algoritmo de questionamento só faz sentido quando o tamanho da entrada aumenta indefinidamente, e a única entrada que pode crescer aqui é 100 - o tamanho da lista; Suponho que a verdadeira questão era "podemos garantir que obtemos o Top N gastando O (1) tempo por número (não O (N) como na solução de seu amigo), é possível?".
A primeira coisa que vem à mente é contar a classificação, que comprará a complexidade do tempo O (1) por número para o problema Top-N pelo preço da utilização do espaço O (m), em que m é o comprimento do intervalo dos números recebidos . Então sim, é possível.
fonte
Use uma fila de prioridade mínima implementada com um heap Fibonacci , que tenha tempo de inserção constante:
fonte
O(log n)
tempo amortizado" , portanto isso ainda resultaria emO(log k)
ondek
está a quantidade de itens a serem armazenados.A tarefa é claramente encontrar um algoritmo que seja O (1) no comprimento N da lista de números necessária. Portanto, não importa se você precisa do número 100 ou 10000, o tempo de inserção deve ser O (1).
O truque aqui é que, embora esse requisito O (1) seja mencionado na inserção da lista, a pergunta não disse nada sobre a ordem do tempo de pesquisa no espaço numérico inteiro, mas acontece que isso pode ser feito O (1) também. A solução é a seguinte:
Organize uma hashtable com números para chaves e pares de ponteiros de lista vinculada para valores. Cada par de ponteiros é o início e o fim de uma sequência de lista vinculada. Normalmente, este será apenas um elemento e depois o próximo. Cada elemento da lista vinculada fica próximo ao elemento com o próximo número mais alto. Portanto, a lista vinculada contém a sequência classificada dos números obrigatórios. Mantenha um registro do número mais baixo.
Pegue um novo número x do fluxo aleatório.
É superior ao último número mais baixo registrado? Sim => Etapa 4, Não => Etapa 2
Bata na tabela de hash com o número acabado de obter. Existe uma entrada? Sim => Etapa 5. Não => Pegue um novo número x-1 e repita esta etapa (esta é uma pesquisa linear descendente simples, aceite aqui, isso pode ser melhorado e eu explicarei como)
Com o elemento list obtido apenas na tabela de hash, insira o novo número logo após o elemento na lista vinculada (e atualize o hash)
Pegue o número mais baixo l registrado (e remova-o da lista / hash).
Bata na tabela de hash com o número acabado de obter. Existe uma entrada? Sim => Etapa 8. Não => Pegue um novo número l + 1 e repita esta etapa (esta é uma pesquisa linear ascendente simples)
Com um acerto positivo, o número se torna o novo número mais baixo. Avance para o passo 2
Para permitir valores duplicados, o hash realmente precisa manter o início e o fim da sequência de lista vinculada de elementos duplicados. Adicionar ou remover um elemento em uma determinada tecla aumenta ou diminui o intervalo apontado.
A inserção aqui é O (1). As pesquisas mencionadas são, acho que algo como, O (diferença média entre números). A diferença média aumenta com o tamanho do espaço numérico, mas diminui com o comprimento necessário da lista de números.
Portanto, a estratégia de pesquisa linear é muito ruim, se o espaço numérico for grande (por exemplo, para um tipo int de 4 bytes, 0 a 2 ^ 32-1) e N = 100. Para contornar esse problema de desempenho, você pode manter conjuntos paralelos de tabelas de hash, onde os números são arredondados para magnitudes mais altas (por exemplo, 1s, 10s, 100s, 1000s) para criar as teclas adequadas. Dessa forma, você pode acelerar e diminuir as marchas para realizar as pesquisas necessárias mais rapidamente. O desempenho então se torna um O (log numberrange), eu acho, que é constante, ou seja, O (1) também.
Para deixar isso mais claro, imagine que você tenha o número 197 em mãos. Você atinge a tabela de hash 10s, com '190', é arredondado para o próximo dez. Qualquer coisa? Não. Então você diminui em 10s até pressionar, digamos, 120. Então você pode começar em 129 na hashtable 1s e tentar 128, 127 até atingir alguma coisa. Agora você encontrou o local na lista vinculada para inserir o número 197. Ao inseri-lo, você também deve atualizar a hashtable 1s com a entrada 197, a hashtable 10s com o número 190, 100s com 100, etc. o que você precisa fazer aqui é 10 vezes o log do intervalo de números.
Talvez eu tenha entendido errado alguns detalhes, mas como essa é a troca de programadores e o contexto foi de entrevistas, espero que o texto acima seja uma resposta suficientemente convincente para essa situação.
EDIÇÃO Adicionei alguns detalhes extras aqui para explicar o esquema de hashtable paralelo e como isso significa que as pesquisas lineares ruins que eu mencionei podem ser substituídas por uma pesquisa O (1). Também percebi que, obviamente, não há necessidade de procurar o próximo número mais baixo, porque você pode ir direto para ele procurando na hashtable com o número mais baixo e progredindo para o próximo elemento.
fonte
Podemos assumir que os números são de um tipo de dados fixo, como Inteiro? Nesse caso, mantenha um registro de cada número adicionado. Esta é uma operação O (1).
Código VB.Net:
Quando você retorna a lista, pode demorar o quanto quiser. Simplesmente itere no final da lista e crie uma nova lista dos 100 valores mais altos registrados. Esta é uma operação O (n), mas é irrelivante.
Edit: Na verdade, não importa se é um tipo de dados fixo. Como não há limites impostos ao consumo de memória (ou disco rígido), você pode fazer isso funcionar para qualquer intervalo de números inteiros positivos.
fonte
Cem números são facilmente armazenados em uma matriz, tamanho 100. Qualquer árvore, lista ou conjunto é um exagero, dada a tarefa em questão.
Se o número recebido for maior que o menor (= último) na matriz, execute todas as entradas. Depois de encontrar o primeiro menor que o seu novo número (você pode usar pesquisas sofisticadas para fazer isso), percorra o restante da matriz, pressionando cada entrada "para baixo" por uma.
Como você mantém a lista classificada desde o início, não é necessário executar nenhum algoritmo de classificação. Este é O (1).
fonte
Você pode usar um binário Max-Heap. Você precisaria acompanhar um ponteiro para o nó mínimo (que pode ser desconhecido / nulo).
Você começa inserindo os 100 primeiros números na pilha. O máximo estará no topo. Depois disso, você sempre manterá 100 números lá.
Então, quando você receber um novo número:
Infelizmente,
findMinimumNode
é O (n) e você incorre nesse custo uma vez por inserção (mas não durante a inserção :). Remover o nó mínimo e inserir o novo nó é, em média, O (1), porque eles tendem para a parte inferior do heap.Indo para o outro lado com um heap mínimo binário, o min está no topo, o que é ótimo para encontrar o min para comparação, mas é péssimo quando você precisa substituir o mínimo por um novo número que seja> min. Isso ocorre porque você deve remover o nó min (sempre O (logN)) e depois inserir o novo nó (O (média 1)). Portanto, você ainda possui O (logN), que é melhor que o Max-Heap, mas não O (1).
Obviamente, se N for constante, você sempre terá O (1). :)
fonte