我想知道流行语言中基本数据结构的空间复杂度。
最佳答案
所有这些都有空间复杂度 O(n)。所有改变的只是系数，这完全取决于实现。特别是当您开始进行诸如预分配空间以降低时间复杂度之类的事情时。
例如，数组列表结构通常会预先分配额外的空间。因此，许多对象的确切复杂性实际上是一个范围，完全取决于实现以及它们的创建和使用方式。例如，如果我编写一个数组列表，每当需要更多空间时，它总是分配三个额外的空间，并且当有超过 5 个开放空间时，总是释放到三个开放空间，那么 n 的实际复杂度将是 [n, n + 5] + 开销。
当编程通常易于使用以及它与您将如何使用它的适合程度时，在这些项目之间进行选择的巨大差异。例如，链表对于随机访问来说很糟糕，但对于迭代来说却很出色。
关于c# - HashTable、Array、ArrayList、LinkedList 等的空间复杂度是多少(如果还有的话)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3104281/