Big O de matrizes JavaScript

Matrizes em JavaScript são muito fáceis de modificar adicionando e removendo itens. De certa forma, ele mascara o fato de que a maioria das matrizes de idiomas tem tamanho fixo e exige operações complexas para resize. Parece que o JavaScript facilita escrever um código de matriz com desempenho insatisfatório. Isso leva à pergunta:

Que desempenho (em termos de grande complexidade de tempo) posso esperar das implementações de JavaScript em relação ao desempenho da matriz?

Eu suponho que todas as implementações razoáveis ​​de JavaScript tenham pelo menos os seguintes grandes O’s.

  • Acesso – O (1)
  • Acrescentando – O (n)
  • Preendendo – O (n)
  • Inserção – O (n)
  • Exclusão – O (n)
  • Troca – O (1)

O JavaScript permite que você preencha um array com um determinado tamanho, usando a new Array(length) syntax new Array(length) . (Bonus question: É criar um array desta maneira O (1) ou O (n)) Isto é mais como um array convencional, e se usado como um array pré-dimensionado, pode permitir O (1) append. Se a lógica buffer circular for adicionada, você poderá obter O (1) antes. Se uma matriz dinamicamente expansível for usada, O (log n) será o caso médio para ambas.

Posso esperar um melhor desempenho para algumas coisas do que minhas suposições aqui? Não espero que nada seja descrito em nenhuma especificação, mas, na prática, pode ser que todas as principais implementações usem matrizes otimizadas nos bastidores. Há expansões dinâmicas de matrizes ou alguns outros algoritmos de aumento de desempenho no trabalho?

PS

A razão pela qual estou me perguntando isso é porque estou pesquisando alguns algoritmos de ordenação, a maioria dos quais parece supor que append e excluir são operações O (1) ao descrever seu O grande geral.

Em contraste com a maioria das linguagens, que implementam matrizes com, bem, matrizes, em JavaScript Arrays são objects, e os valores são armazenados em um hashtable, assim como os valores de objects regulares. Assim sendo:

  • Acesso – O (1)
  • Appending – Amortized O (1) (às vezes é necessário resize o hashtable; normalmente, apenas é necessária a inserção)
  • Prepending – O (n) via unshift , uma vez que requer a reatribuição de todos os índices
  • Inserção – O Amortizado (1) se o valor não existir. O (n) se você quiser deslocar valores existentes (por exemplo, usando splice ).
  • Exclusão – Amortizado O (1) para remover um valor, O (n) se você quiser reatribuir índices via splice .
  • Troca – O (1)

Em geral, a configuração ou a desativação de qualquer chave em um dict é amortizada como O (1), e o mesmo vale para matrizes, independentemente de qual seja o índice. Qualquer operação que requer a renumeração dos valores existentes é O (n) simplesmente porque você precisa atualizar todos os valores afetados.

Todas as complexidades que você mencionou parecem boas. Mas se o object da matriz mantiver o tamanho, então o acréscimo também pode ser feito no tempo O (1).