问题标签 [space-complexity]

假设我有大小为 N 的数据（即 N 个元素），并且字典是用容量 N 创建的。复杂性是什么：

• 空间——整个字典
• time -- 向字典中添加条目

MS 仅显示条目检索接近 O(1)。但是其余的呢？

这是使用 DP 方法找到最大连续子序列和的算法。该算法似乎很好，但有人提到这具有空间复杂度 O(n)。为什么？

对我来说，这个算法似乎有 O(1) 的空间复杂度。我想问的另一件事是，在不使用任何类型递归的算法的情况下，除了恒定的空间复杂度之外，它是否还有可能具有其他任何东西？

假设我们有 m 组S1,S2,...,Sm元素来自{1...n} Given that m=O(n) ，在 O(n) 时间和空间|S1|+|S2|+...+|Sm|=O(n) 内对所有集合进行排序。O(n)

我正在考虑在每组上使用计数排序算法。对每个集合进行计数排序O(S1)+O(S2)+...+O(Sm) < O(n) ，因为在最坏的情况下，如果一个集合由 n 个元素组成，它仍然需要 O(n)。

但它会解决问题并仍然坚持它只使用 O(n) 空间吗？

我有个问题。

就理论计算机科学而言，当我们分析一个算法时，如果一个算法初始化了一个新的数据结构，那么我们将这个数据结构视为空间复杂度的一部分。

现在我不太确定这部分。

假设我有一个数组，int我想通过使用int指针映射来映射它们。如

如果这个算法没有使用指针，那么我们可以清楚地说明它正在初始化一个大小为 n 的映射，因此空间复杂度是 O(n)，但是对于这种情况，我们使用指针，空间复杂度是多少这个算法？

内容

1. 问题陈述
2. 详细说明和示例
3. 访问的资源
4. 答案（发布时）
5. 后续问题（按照他们的设想）

问题

在计算“空间（内存）复杂度”的大 O 样式符号时，如何考虑原始类型的大小？

详细说明和示例

如果我分配一个长度为 N 个元素的数组，并且每个元素都是一个 32 位整数，那么我大概分配了大约 N*32 位。据我了解，这种分配的内存复杂度被认为是 O(N)。

使用上面的示例，如果我将数组中的每个元素视为指向唯一链表的指针，其中链表的长度为 1（包含 1 个节点和一个空指针），并且该节点的数据段也是 32 -bit 整数，我现在显然正在分配：

1. 32 位数组元素
2. 32位链表数据
3. 32位链表空指针

我的数组变成 O(3*32*N) 了吗？我知道这仍将被视为 O(N)，但正如您所看到的，在时间/内存权衡变得相关的情况下，知道差异是相关的（例如，我可以使用各种长度的链表和存储在元素中的头指针数组以延迟我必须动态调整数组大小的点，因为我只能延长链表 - 这会将插入操作摊销到 O(1)，但会大大增加内存复杂性，直到实际发生调整大小，其中链表将恢复为数组中的元素，因此消耗的内存大大减少）

已访问的资源：

Stack Overflow 上的相关问题：

内存使用对算法复杂性的影响

为什么 A* 的复杂性在内存中是指数级的？

维基书有以下说法：

http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

此外，维基百科详细阐述了这个主题：

http://en.wikipedia.org/wiki/Big_O_notation

答案

后续问题

对于一个类项目，我们需要找到一个基于循环动态数组的优先级队列的最优增长因子。我进行了一些测试，但没有结果。我们被告知有一种数学方法可以显示它，但我在任何地方都找不到。

我查了一下，发现 Java ArrayList 使用 3/2，pyhton 的列表也有 ac 实现，它使用 9/8 因子，基本上我认为它在不同的编程语言之间有所不同。

那么是否有任何数学方法可以找到动态数组的“最佳”增长因子？

我正在寻找似乎非常适合我的项目需求的番石榴TreeRangeMap 。java文档说这是基于（java标准？）TreeMap，它有O（log（n））时间来获取，放置和下一步。

但是 TreeRangeMap 应该是某种范围树实现，根据这个SO question，查询的时间复杂度为 O(k + log(n))，空间为 O(n)，k 是范围大小？有人可以证实这一点吗？

我对TreeRangeMap.subRangeMap()操作的时间复杂度也很感兴趣。它是否具有相同的 O(k + log(n))？

谢谢。

考虑一下，在包含元素的情况下Merge Sort，int Array我们n需要一个额外的大小数组n来执行合并。尽管我们最终丢弃了额外的数组。所以合并排序的空间复杂度是O(n)。但是如果你看一下递归mergeSort过程，每次递归调用都会将mergeSort(something)一个堆栈帧添加到堆栈中。它确实需要一些空间，对吧？

我的问题是：

1. 为什么我们在计算合并排序复杂度时不考虑堆栈帧的大小？
2. 是不是因为堆栈只包含几个整数变量和一个引用，不占用太多内存？
3. 如果我的递归函数创建了一个新的本地数组（比如说int a[]=new int [n];）。那么在计算空间复杂度时会考虑它吗？

I am not good at determining time and memory complexities and would appreciate it if someone could help me out.

I have an algorithm, here and I am not sure what its time and memory complexities would be.

What is its time and memory complexity and why?

Thanks

您好，我尝试计算 IDS（迭代加深深度优先搜索）算法的空间复杂度，但我无法弄清楚如何做到这一点。我无法真正理解算法如何访问树的节点，以便我可以计算它需要多少空间。你能帮助我吗？