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

Preciso escrever um RandomQueue que permita anexos e remoção aleatória em Constant Time (O (1)).

Meu primeiro pensamento foi apoiá-lo com algum tipo de Array (eu escolhi um ArrayList), pois os arrays têm acesso constante por meio de um índice.

Examinando a documentação, porém, percebi que as adições de ArrayLists são consideradas Tempo constante amortizado, pois uma adição pode exigir uma realocação da matriz subjacente, que é O (n).

O Tempo Constante Amortizado e o Tempo Constante são efetivamente os mesmos ou preciso examinar uma estrutura que não exija uma realocação completa de todas as adições?

Estou perguntando isso porque estruturas baseadas em array de lado (que, até onde eu sei, sempre terão adições de tempo constante amortizado), não consigo pensar em nada que atenda aos requisitos:

• Qualquer coisa baseada em árvore terá, na melhor das hipóteses, acesso O (log n)
• Uma lista vinculada pode potencialmente ter adições de O (1) (se uma referência à cauda for mantida), mas uma remoção aleatória deve ser, na melhor das hipóteses, O (n).

Aqui está a pergunta completa; no caso de ver alguns detalhes importantes:

Projete e implemente um RandomQueue. Esta é uma implementação da interface da Fila, na qual a operação remove () remove um elemento escolhido uniformemente aleatoriamente entre todos os elementos atualmente na fila. (Pense em um RandomQueue como uma bolsa na qual podemos adicionar elementos ou acessar e remover cegamente algum elemento aleatório.) As operações add (x) e remove () em um RandomQueue devem ser executadas em tempo constante por operação.

O tempo constante amortizado quase sempre pode ser considerado equivalente ao tempo constante e, sem conhecer as especificidades do seu aplicativo e o tipo de uso que você planeja fazer nessa fila, é mais provável que você esteja coberto.

Uma lista de matrizes tem o conceito de capacidade , que é basicamente igual ao maior tamanho / comprimento / contagem de itens que já foram exigidos até agora. Portanto, o que acontecerá é que, no início, a lista de matrizes continuará se realocando para aumentar sua capacidade à medida que você continua adicionando itens, mas em algum momento 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). Nesse ponto, a matriz deixará de se realocar e todos os anexos serão atendidos no tempo constante de O (1).

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

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

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

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

Em aplicações críticas de resposta, esses horários podem ser inaceitáveis. Se você precisar de uma garantia de retorno em pouco tempo, não poderá confiar em um algoritmo que ocasionalmente excederá isso. Já trabalhei nesses projetos antes, mas eles são extremamente raros.

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

* Há um pouco de um problema aqui. Para fazer com que qualquer contêiner de uso geral tenha tempo constante para 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.

Depende - se você está otimizando a taxa de transferência ou a latência:

• Os sistemas sensíveis à latência precisam de desempenho consistente. Para esse cenário, precisamos enfatizar o pior comportamento do sistema. Exemplos são sistemas flexíveis em tempo real, como jogos que desejam obter uma taxa de quadros consistente ou servidores da Web que precisam enviar uma resposta dentro de um determinado prazo: desperdiçar ciclos de CPU é melhor do que chegar atrasado.
• Os sistemas com taxa de transferência otimizada não se importam com paradas ocasionais, desde que a quantidade máxima de dados possa ser processada a longo prazo. Aqui, estamos principalmente interessados ​​no desempenho amortizado. Geralmente é o caso de trituração de números ou outros trabalhos de processamento em lote.

Observe que um sistema pode ter componentes diferentes que devem ser categorizados de maneira diferente. Por exemplo, um processador de texto moderno teria um thread de interface do usuário sensível à latência, mas threads otimizados para taxa de transferência 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 pensar: quando um problema é limitado a um determinado número, as características de desempenho reais e medidas são mais importantes que o comportamento "para n muito grande ".

Se você for solicitado para um algoritmo "amortizado constante de tempo", o algoritmo pode às vezes levar um longo tempo. Por exemplo, se você usar std :: vector em C ++, esse vetor poderá ter espaço alocado para 10 objetos e, quando você alocar o 11º objeto, será alocado espaço para 20 objetos, 10 objetos serão copiados e o 11º será adicionado. 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 você for solicitado a usar um algoritmo de "tempo constante", ele sempre deve ser rápido, para cada operação. Isso seria importante para sistemas em tempo real, onde você pode precisar de uma garantia de que cada operação seja sempre rápida. Frequentemente, o "tempo constante" não é necessário, mas definitivamente não é o mesmo que o "tempo constante amortizado".