JavaScript中“设置并映射"的时间复杂度 [英] Time complexity of Set and Map in javascript

问题描述

Set&中基本操作的时间复杂度是多少?用JavaScript映射?

它们在哈希表还是BST中?

解决方案

根据关于集和地图的ECMA文档(

您将找到Maps，WeakMaps和WeakSets的相似句子.因此，您应该期望时间复杂度是次线性的.另外，您可以在 Javascript ES6集合的计算/时间复杂度

What is time complexity of basic operation in Set & Map in javascript?

Are they in hashmaps or BSTs?

解决方案

According to the ECMA documentation for Set and Maps (http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects):

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection. The data structures used in this Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

You will find similar sentences for Maps, WeakMaps and WeakSets. So, you should expect the time-complexity to be sublinear. Also, you can check out a solution on Javascript ES6 computational/time complexity of collections

这篇关于JavaScript中“设置并映射"的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！