例如,使用HashSet
,我知道获得一个已知元素通常是O(1),但是我想找出获得所有元素的时间复杂度是什么(不知道它们,因此是一个迭代)。
我在标准库的文档中找不到任何信息。我也看过SwissTable,但没有成功。
它甚至可以测量吗?在哪里可以找到它?
最佳答案
TL; DR :
BTreeSet
:O(N)HashSet
:O(容量)B树集
对于某些K值,B树数据结构是由K个元素组成的数组树。
树的深度为O(log N),并且当节点的数组不足时,它们会合并在一起。对于我们的情况,我们可以使用以下规则:尽管任何常量都可以工作,但节点必须至少是半满的。
通常,迭代是从最小到最大完成的,这是有序遍历。这意味着从元素到下一个元素的移动并不是严格意义上的O(1),实际上,从左子树的最右边的元素到根元素的移动意味着O(log N)步。
可以证明,摊销的复杂度为O(1),这导致O(N)的整体遍历复杂度。
哈希集
哈希映射或哈希集没有一般的迭代复杂性;它因实现而异。
Rust的实现本质上是一个开放式哈希表。这意味着大量的K元素(K =容量),或多或少稀疏。
与大多数开放式哈希表一样,迭代没有短路。而是依次检查数组的每个元素。
因此,迭代时间与容量成正比,而与元素的数量无关。在稀疏填充的哈希表上,这非常昂贵。
注意:Swiss表使用开放式哈希表的变体,这不会影响各种操作的基本属性。
关于algorithm - 迭代BTreeSet和HashSet的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62558996/