我对程序的空间复杂度存有疑问。假设我正在迭代一个大小为 n(可能以十亿为单位)的数组(存储事件 ID)。我想跟踪每个事件 ID 的发生,所以我使用 HashMap 将事件 ID 存储为键,并将其发生计数器存储为值。
伪代码如下:
Map m = HashMap<>
for i to n-1
if m.contains(i)
int prevCount = m.get(i)
m.put(i, prevCount +1)
else
m.put(i, 1)
空间复杂度是多少?
PS 这是我在 stackoverflow 中的第一个问题,如果它看起来重复,请引导我找到正确答案。
最佳答案
您的循环最多将 n-1 个键/值对添加到 HashMap
。
因此,空间复杂度为O(n)
,因为HashMap
内部存储由一个数组组成,其大小将达到接近n的2的幂(假设你没有给 HashMap
一个比 n
大得多的初始容量,数组的每个元素都是一个链表,O(1 )
平均元素数。
关于java - 以线性时间迭代数组时 HashMap 的空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27334494/