Complexidade de tempo de inserção na lista vinculada

Question

Desculpas Se esta questão parecer uma verificação de solução, mas esta questão foi feita no meu teste de admissão de pós-graduação e há muito montando nisso:

.

Qual é a pior complexidade do tempo de inserção de $ n $ em uma lista vinculada vazia, se a lista vinculada precisar ser mantida em ordem classificada? .

Na minha opinião, a resposta deve ser $ o (n ^ 2) $ porque em todas as inserções, teremos que inserir o elemento no lugar certo e É possível que cada elemento tenha que ser inserido no último lugar, me dando uma complexidade de tempo da $ 1 + 2 + ... (N-1) + n= O (n ^ 2) $

No entanto, a solução que eu digo que podemos primeiro classificar os elementos em $ o (n \ log n) $ e, em seguida, podemos inseri-los um por um em $ O (n) $ , dando-nos uma complexidade geral da $ O (n \ log n) $ < / span>.

Da formulação dada da questão, qual solução é mais apto? Na minha opinião, uma vez que a questão menciona "a lista vinculada precisa ser mantida em ordem classificada", estou inclinado a dizer que não podemos classificar os elementos de antemão e insira-os na ordem classificada.

Answer 1

A questão diz apenas que a lista de destino precisa ser mantida em ordem classificada. Não diz nada sobre qualquer outra estrutura de dados que você possa escolher. A solução proposta primeiro faz algum pré-processamento dos argumentos para inserir, então a inserção é adequada. Isso é permitido pela declaração do problema.

Um motivo prático para fazer isso, em vez de inserir os elementos e classificar, seria se o objeto Lista vinculado for compartilhado com outro thread que exija sempre ser classificado sempre. (Em tal cenário, você precisaria garantir que a inserção de um elemento seja atômico.) Então esta questão não está apenas fazendo exigências estranhas para ser estranho. É o tipo de requisitos que chegam frequentemente no mundo real da programação.

Outra solução com a mesma complexidade seria inserir os elementos na lista de destino à medida que eles vêm e manter um valores de elemento de mapeamento de estrutura de dados paralelos para ponteiros de nó na lista de destino. Para inserir cada elemento, encontre o elemento anterior no mapeamento e insira o novo elemento após este nó. Isso pressupõe que o processo de inserção cria os nós da lista como vai (em oposição ao preenchimento de nós em branco existentes).

Esta questão é mais sobre a compreensão da leitura do que sobre os algoritmos. A maneira como é redigida, é um pouco de pergunta de truque. É um pouco fraco porque depende da leitura precisa, mas não declara algumas suposições importantes, como o fato de que obter os elementos para inserir custos $ O (n) $ comparando dois elementos podem ser feitos em $ O (1) $ , e o domínio de entrada é efetivamente ilimitado (exercício: venha com uma matemática $ o (n) $ algoritmo se as entradas forem inteiros no intervalo $ [1,42] $ ). Mas a resposta dada está correta.

Você fez a suposição de que não há como usar uma estrutura de dados auxiliares. Nada na declaração de problemas proíbe o uso de estruturas de dados auxiliares. Uma maneira simples de proibir as estruturas de dados auxiliares seria necessitar de $ o (1) $ sobrecarga de memória.

Observe que, mesmo sob essa suposição, seu raciocínio é errado, ou pelo menos impreciso. Se você achou saber que os elementos são dados na ordem correta, você pode manter um ponteiro para a cauda da lista e continuar inserindo lá, o que levaria $ O (n) $ . O pior caso não é se cada elemento deve ser inserido na última posição na lista de alvos, mas na última posição alcançada ao atravessar a lista de alguma forma. O pior caso é de fato $ \ theta (n ^ 2) $ , mas para provar isso, você tem que provar que encontrar o ponto de inserção na lista de $ \ theta (n) $ tempo, e isso requer provar que a distância de Qualquer ponteiro você tem na lista é limitada abaixo por $ \ ômega (n) $ . Este é o caso se você tiver um número constante $ a $ de ponteiros (você implicitamente assumiu $ a= 1 $ , com um único ponteiro no início da lista), para que você precise atravessar pelo menos $ k / a $ nós após a matemática $ k $ inserções no pior caso.

Answer 2

melhor estrutura possível que eu conheço, são montes de Fibonacci, você pode inserir elementos em $ O (1) $ e extrair o mínimo em $ o (\ log (n)) $ , isto significa se você precisar de uma ordem classificada de todos os elementos, leva você $ o (n \ log(n)) $ Enquanto inserir novos elementos só custa você $ o (1) $ , eu não conheço outra estrutura que possa acompanhar isso.

Answer 3

É realmente uma pergunta complicada.Primeiro de tudo, a complexidade de O (nlogn) aplica-se apenas pelos algoritmos que usam comparação entre seus elementos (algoritmo comparativo).Há também algoritmos que não são comparativos, como a Radix, que sua complexidade depende do tamanho em bits que os números precisam ser armazenados na memória.Então, se assumirmos que podemos classificar os números de antemão com qualquer algoritmo, então podemos também assumir que os números são naturais e o elemento máximo é m <10, então com o tipo de radix você teria pior caso O (10n)= O (10N)= O (10N)=n).Se não podemos fazer nenhuma suposição, então você está certo.Se você só tem permissão para usar listas vinculadas e nada mais (sem indexação de qualquer tipo), então a complexidade é O (n ^ 2) (Bubble Sort).

Answer 4

Deve ser O (n). Siga o algoritmo como -

1) Se a lista vinculada estiver vazia, faça o nó como cabeça e devolvê-lo.

2) Se o valor do nó for inserido for menor do que o valor do nó da cabeça e insira o nó no início e torná-lo cabeça.

3) Em um loop, encontre o nó apropriado depois qual o nó de entrada deve ser inserido.

Para encontrar o início do nó apropriado da cabeça, Continue movendo até chegar a um nó que o valor é maior que o nó de entrada.O nó antes disso é o nó apropriado

4) Insira o nó após o nó apropriado encontrado no passo 3