Big O de tableaux JavaScript

Question

Les tableaux en JavaScript sont très faciles à modifier par l'ajout et la suppression d'éléments. Elle a un peu masqué par le fait que la plupart des langues de la matrice sont de taille fixe, et nécessitent des opérations de redimensionnement. Il semble que JavaScript permet d'écrire facilement mal l'exécution de la matrice de code. Cela conduit à la question:

Quelles sont les performances (en termes de big O moment de la complexité) puis-je m'attendre à partir de JavaScript implémentations en ce qui concerne les performances de la baie?

Je suppose que toutes les implémentations de JavaScript ont au moins les éléments suivants big O est.

• Accès - O(1)
• Ajout - O(n)
• Ajoutant - O(n)
• D'Insertion, en O(n)
• Suppression - O(n)
• La Permutation - O(1)

JavaScript permet de pré-remplir un tableau à une certaine taille, à l'aide de new Array(length) de la syntaxe. (Question Bonus: Est la création d'un tableau de cette manière O(1) O(n)) C'est plus comme un réseau classique, et si elle est utilisée comme un pré-tableau de taille, peut permettre à O(1) en ajoutant. Si le tampon circulaire logique est ajouté, vous pouvez atteindre O(1) faire précéder. Si une extension dynamique de tableau est utilisé, O(log n) est la moyenne des cas pour les deux.

Puis-je espérer de meilleures performances pour certaines choses que mes suppositions? Je n'attends rien est indiqué dans les spécifications, mais dans la pratique, il se pourrait que toutes les grandes implémentations à l'utilisation optimisée des tableaux de derrière les coulisses. Existe-il une expansion dynamique de tableaux ou de quelque autre matière d'augmentation des performances des algorithmes au travail?

P. S.

La raison pour laquelle je me demande c'est parce que je suis à la recherche de quelques algorithmes de tri, dont la plupart semblent assumer l'ajout et la suppression sont en O(1) opérations lors de la description de l'ensemble de leurs big O.

Answer 1

Contrairement à la plupart des langues, qui mettent en œuvre des tableaux avec les, bien, les tableaux, les Tableaux Javascript sont des objets, et les valeurs sont stockées dans une table de hachage, comme des valeurs de l'objet. En tant que tel:

• Accès - O(1)
• Ajoutant Amorti O(1) (parfois le redimensionnement de la table de hachage est requis; il est habituellement seulement d'insertion est requise)
• Ajoutant - O(n) par unshift, car il nécessite la réaffectation de tous les indices
• D'Insertion - Amorti O(1) si la valeur n'existe pas. O(n) si vous souhaitez modifier les valeurs existantes (par exemple, en utilisant splice).
• Suppression Amorti O(1) pour supprimer une valeur, O(n) si vous voulez réaffecter les indices via splice.
• La Permutation - O(1)

En général, le réglage ou la suppression de n'importe quelle touche dans un dict est amorti O(1), et il en va de même pour les tableaux, indépendamment de ce que l'indice est. Une opération qui requiert la renumérotation des valeurs existantes est O(n) tout simplement parce que vous devez mettre à jour tous les affectés de valeurs.

Answer 2

Toutes les complexités que vous avez mentionnées semblent bien. Mais si l'objet tableau conserve la longueur, l'ajout peut également être effectué en un temps O (1).