algorithm - 将列表复制到 HashSet 的算法的空间复杂度

Question

将列表中的每个元素放入 HashSet 的算法的空间复杂度是多少？是 O(n)，其中 n 是列表的大小，还是 O(k)，其中 k 是列表中唯一元素的数量。由于 HashSet 只有在我们向其添加唯一元素时才会增长，所以在我看来后者是正确的。

Answer 1

任何算法的空间复杂度都会考虑输入的大小。它是算法执行期间所需的最大工作内存的度量。因此，对于 O(n) 大小的输入，空间复杂度必须至少为 O(n)。 Source

鉴于算法仅对输入使用 O(n)，这并不是一个非常糟糕的实现，即它在遍历列表时使用恒定量的空间，我们知道 k < n，因此输入大小永远是空间复杂度的主导因素。所以整体空间复杂度将是 O(n)。