O tempo constante e o tempo constante amortizado são efetivamente considerados equivalentes?

O tempo constante amortizado quase sempre pode ser considerado equivalente ao tempo constante e sem saber as especificações de sua aplicação e o tipo de uso que você está planejando fazer esta fila, é mais provável que você seja coberto.

Uma lista de arrays tem o conceito de capacidade , que é basicamente igual ao maior tamanho / comprimento / contagem de itens que alguma vez foi exigida dele até agora. Então, o que acontecerá é que no início a lista de matriz continuará se realocando para aumentar sua capacidade conforme você adiciona itens a ela, mas em algum ponto o número médio de itens adicionados por unidade de tempo inevitavelmente corresponderá ao número médio de itens removido por unidade de tempo, (caso contrário, você acabaria ficando sem memória de qualquer maneira), ponto em que a matriz irá parar de se realocar e todos os anexos serão encontrados no tempo constante de O (1).

No entanto , tenha em mente que, por padrão, a remoção aleatória de uma lista de array não é O (1), é O (N), porque as listas de array movem todos os itens após o item removido uma posição para baixo para tomar o lugar do item removido . Para obter O (1), você terá que substituir o comportamento padrão para substituir o item removido por uma cópia do último item da lista de matriz e, em seguida, remover o último item, de forma que nenhum item seja movido. Mas então, se você fizer isso, você não terá mais uma fila exatamente.

Comentários

• Droga, bom ponto sobre remoções; Eu não ‘ não considerei isso. E como ‘ removemos elementos aleatoriamente, não ‘ isso significa tecnicamente ‘ não é mais uma fila nesse sentido?
• Sim, significa que você não a está tratando realmente como uma fila. Mas não sei como você planeja encontrar os itens a serem removidos. Se seu mecanismo para localizá-los espera que eles estejam presentes na fila na ordem em que foram adicionados, você está sem sorte.Se você não se importa se a ordem dos itens ficar distorcida, tudo bem.
• A expectativa é que meu RandomQueue implemente o Queue interface, e para o método remove fornecido para remover aleatoriamente em vez de estourar a cabeça, então não deveria ‘ Não há como confiar em um pedido específico. Eu acho que, dada a natureza aleatória disso, então, o usuário não deve ‘ esperar que ele mantenha uma ordem específica. Citei a tarefa na minha pergunta para esclarecimento. Obrigado.
• Sim, então, parece que você ficará bem se apenas certificar-se de que a remoção do item seja feita da maneira que sugeri.
• Uma última coisa se você não ‘ t mente. Eu ‘ pensei mais, e não ‘ parece que ‘ É possível ter ” true ” O (1) adições e ” true ” O (1) remoção aleatória; ele ‘ será uma troca entre os 2. Você pode ter uma estrutura alocada individualmente (como uma matriz) que fornece remoção, mas não acréscimo, ou uma estrutura alocada por blocos como um Linked- Lista que fornece acréscimos, mas não remove. Isso é verdade? Mais uma vez, obrigado.

A pergunta parece pedir especificamente um tempo constante, e não um tempo constante amortizado . Portanto, com relação à questão citada, não, eles não são efetivamente os mesmos *. No entanto, eles estão em aplicativos do mundo real?

O problema típico com a constante amortizada é que, ocasionalmente, você precisa pagar a dívida acumulada. Portanto, embora as inserções sejam geralmente constantes, às vezes você tem que sofrer a sobrecarga de reinserir tudo novamente quando um novo bloco é alocado.

Onde a diferença entre o tempo constante e o tempo constante amortizado é relevante para um aplicativo depende se esta velocidade muito lenta ocasional é aceitável. Para um grande número de domínios, geralmente não há problema. Especialmente se o contêiner tiver um tamanho máximo efetivo (como caches, buffers temporários, contêineres de trabalho), você poderá efetivamente pagar pelos custos apenas uma vez durante a execução.

Em resposta a aplicativos críticos, esses tempos podem ser inaceitáveis. Se você for obrigado a cumprir uma garantia de retorno de curto prazo, você não pode confiar em um algoritmo que ocasionalmente irá exceder isso. Já trabalhei nesses projetos antes, mas eles são extremamente raros.

Também depende de quão alto esse custo realmente é. Os vetores tendem a ter um bom desempenho, pois seu custo de realocação é relativamente baixo. No entanto, se você for para o mapa hash, a realocação pode ser muito maior. Embora, novamente, para a maioria dos aplicativos provavelmente bom, especialmente servidores de vida mais longa com um limite superior nos itens no contêiner.

* Há um pequeno problema aqui. Para fazer qualquer contêiner de uso geral ser tempo constante para a inserção, uma das duas coisas deve ser mantida:

• O contêiner deve ter um tamanho máximo fixo; ou
• você pode assumir que a alocação de memória de elementos individuais é tempo constante .

Comentários

• ” servidor de fígado ” parece uma frase estranha para usar aqui. Você quer dizer ” servidor ativo ” talvez?

Depende – se você está otimizando para taxa de transferência ou para latência:

• Latência- sistemas sensíveis precisam de desempenho consistente. Para tal cenário, temos que enfatizar o comportamento do pior caso do sistema. Exemplos são sistemas de tempo real soft, como s jogos que desejam atingir uma taxa de quadros consistente ou servidores da web que precisam enviar uma resposta dentro de um determinado período de tempo: desperdiçar ciclos de CPU é melhor do que atrasar.
• Sistemas otimizados de rendimento não se importam com paralisações ocasionais, desde que a quantidade máxima de dados possa ser processada a longo prazo. Aqui, estamos principalmente interessados no desempenho amortizado. Este é geralmente o caso de processamento de números ou outros trabalhos de processamento em lote.

Observe que um sistema pode ter diferentes componentes que devem ser categorizados de forma diferente. Por exemplo. um processador de texto moderno teria um thread de IU sensível à latência, mas threads otimizados para outras tarefas, como verificação ortográfica ou exportação de PDF.

Além disso, a complexidade algorítmica geralmente não importa tanto quanto poderíamos pense: quando um problema é limitado a um determinado número, as características de desempenho reais e medidas são mais importantes do que o comportamento “para n muito grande”.

Comentários

• Infelizmente, tenho muito poucos antecedentes.A pergunta termina com: ” As operações add (x) e remove () em um RandomQueue devem ser executadas em tempo constante por operação “.
• @Carcigenicar a menos que você saiba com certeza que o sistema é sensível à latência, usar a complexidade amortizada para selecionar uma estrutura de dados deve ser absolutamente suficiente.
• Tenho a impressão de que pode ser um exercício de programação ou um teste. E certamente não é fácil. Absolutamente verdade que raramente importa.

Se for solicitado um “tempo constante amortizado” algoritmo, seu algoritmo pode às vezes demorar muito. Por exemplo, se você usar std :: vector em C ++, tal vetor pode ter alocado espaço para 10 objetos, e quando você aloca o 11º objeto, espaço para 20 objetos é alocado, 10 objetos são copiados e o 11º adicionado, que leva um tempo considerável. Mas se você adicionar um milhão de objetos, poderá ter 999.980 operações rápidas e 20 lentas, com o tempo médio sendo rápido.

Se for solicitado um algoritmo de “tempo constante”, seu algoritmo deve sempre ser rápido, para cada operação. Isso seria importante para sistemas de tempo real, onde você pode precisar de uma garantia de que cada operação será sempre rápida. “Tempo constante” muitas vezes não é necessário, mas definitivamente não é o mesmo que “tempo constante amortizado”.