Quelle est la complexité temporelle des opérations de collecte ES6 ?

ES6 Collections Computational/Time Complexity

ES6 a introduit plusieurs nouveaux types de collections (Set, Map, WeakSet, WeakMap), et la question se pose concernant leur complexité temporelle. Plus précisément, s'ils étaient obligés d'utiliser des algorithmes de temps linéaire (O(n)).

La spécification du langage ECMAScript 2015 n'exige pas explicitement la complexité O(n) pour ces opérations. Il précise que « Les objets d'ensemble doivent être implémentés à l'aide de mécanismes qui, en moyenne, fournissent des temps d'accès sous-linéaires sur le nombre d'éléments de la collection. »

Cela permet l'utilisation d'algorithmes plus efficaces, tels que tables de hachage, qui fournissent un accès en temps constant (O(1)) en moyenne. Bien que cela ne soit pas explicitement requis par la spécification, il est fort probable que des implémentations telles que V8 et JavaScriptCore utilisent des algorithmes aussi efficaces.

Cette explication correspond aux attentes de la plupart des développeurs qui supposent que des algorithmes performants seraient utilisés dans ces implémentations. , garantissant la complexité O(1) pour les opérations telles que Set.prototype.has, add et delete.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!