问题标签 [space-complexity]

所以; 我是一个正在尝试通过 SICP 工作的爱好者（它是免费的！），第一章中有一个示例程序，旨在计算用美国硬币找零的可能方法；(change-maker 100) => 292. 它的实现如下：

反正; 这是一个树递归过程，作者“作为一个挑战离开”找到一个迭代过程来解决相同的问题（即固定空间）。在感到沮丧之后，我没有运气弄清楚这一点或找到答案。我想知道这是我的脑放屁，还是作者在和我开玩笑。

我正在做的这个程序是关于一个社交网络的，这意味着有用户和他们的个人资料。配置文件结构是UserProfile.

现在，有各种可能的 Graph 实现，我认为我使用的不是最好的。我有一个Graph结构，里面有一个指向 type 的链表的指针Vertex。每个Vertex元素都有一个值、一个指向下一个元素的指针Vertex和一个指向类型链表的指针Edge。每个Edge元素都有一个值（所以我可以定义权重和需要的任何东西）、一个指向下一个元素的指针Edge和一个指向Vertex所有者的指针。

我有 2 个示例文件，其中包含要处理的数据（以 CSV 样式）并插入到图表中。第一个是用户数据（每行一个用户）；第二个是用户关系（用于图表）。第一个文件很快被插入到图表中，因为我总是在头部插入并且有大约 18000 个用户。第二个文件需要很长时间，但我仍然在头部插入边缘。该文件有大约 520000 行用户关系，需要 13-15 分钟才能插入到图表中。我做了一个快速测试，读取数据非常快，真的是瞬间。问题在于插入。

存在这个问题是因为我有一个用顶点的链表实现的 Graph。每次我需要插入关系时，我都需要查找 2 个顶点，以便将它们链接在一起。这就是问题所在......为〜520000个关系执行此操作需要一段时间。

我应该如何解决这个问题？

解决方案 1）有人建议我将 Graph（顶点部分）实现为数组而不是链表。这样我就可以直接访问每个顶点，并且插入可能会大大减少。但是，我不喜欢使用 [18000] 元素分配数组的想法。这有多实用？我的样本数据有 ~18000，但如果我需要更少或更多怎么办？链表方法具有这种灵活性，只要有内存，我就可以拥有我想要的任何大小。但是数组没有，我将如何处理这种情况？你有什么建议？

使用链表有利于空间复杂度，但不利于时间复杂度。使用数组有利于时间复杂度，但不利于空间复杂度。

关于这个解决方案的任何想法？

解决方案 2）这个项目还要求我有某种数据结构，允许基于名称索引和 ID 索引进行快速查找。为此，我决定使用哈希表。我的表是通过单独的链接作为冲突解决方案实现的，当达到 0.70 的负载因子时，我通常会重新创建表。我将下一个表大小基于此Link。

目前，两个哈希表都持有一个指向UserProfile而不是重复用户配置文件本身的指针。那将是愚蠢的，更改数据将需要 3 次更改，这样做真的很愚蠢。所以我只是将指针保存到UserProfile. 相同的用户配置文件指针也保存为每个 Graph 中的值Vertex。

所以，我有 3 个数据结构，一个 Graph 和两个 Hash Tables，每一个都指向同一个 exact UserProfile。Graph 结构将用于查找最短路径和类似的东西，而 Hash Tables 用作按名称和 ID 的快速索引。

我正在考虑解决我的 Graph 问题是，而不是让 Hash Tables 值指向 ，而是将其UserProfile指向相应的Vertex. 它仍然是一个指针，没有更多也没有更少的空间使用，我只是改变我指向的内容。

像这样，我可以轻松快速地查找我需要的每个顶点并将它们链接在一起。这将很快插入 ~520000 个关系。

我想到了这个解决方案，因为我已经有了哈希表并且我需要它们，那么，为什么不利用它们来索引 Graph 顶点而不是用户配置文件呢？基本上是一样的，我仍然可以UserProfile很快访问，只需转到Vertex然后到UserProfile.

但是，您认为第二个解决方案与第一个解决方案相比有什么缺点吗？还是只有在第一个解决方案中胜过利弊的利弊？

其他解决方案）如果您有任何其他解决方案，我会全力以赴。但是请解释一下该解决方案与前两个相比的优缺点。我现在真的没有太多时间可以浪费在这个问题上，我需要继续这个项目，所以，如果我这样做的话改变，我需要确切地了解要改变什么，如果这真的是要走的路。

希望没有人在阅读这篇文章后睡着了并关闭了浏览器，对于大遗嘱感到抱歉。但我真的需要决定如何解决这个问题，我真的需要做出改变。

PS：在回答我提出的解决方案时，请像我一样列举它们，这样我就知道你在说什么，并且不要比我现在更迷惑我自己。

我遇到了以下问题。

给定一个包含n 个元素的数组和一个整数k，其中k < n。元素 { a ₀ ... a _k } 和 { a _{k +1} ... a _n } 已经排序。给出一个在 O( n ) 时间和 O(1) 空间中排序的算法。

在我看来，它似乎不能在 O( n ) 时间和 O(1) 空间内完成。问题似乎真的是在询问如何就地进行合并排序的合并步骤。如果可能的话，合并排序不会以这种方式实现吗？我无法说服自己，需要一些意见。

这是一个非常有名的跨国公司问我的问题。问题如下...

输入 0 和 1 的 2D N*N 数组。如果 A(i,j) = 1，则第 i 行第 j 列对应的所有值都将为 1。如果已经有 1，则保持为 1。

例如，如果我们有数组

我们应该得到输出

输入矩阵是稀疏填充的。

这可能在小于 O(N^2) 的时间内完成吗？

没有提供额外的空间是另一个条件。我想知道是否有一种方法可以使用空间 <= O(N) 来实现复杂性。

PS：我不需要复杂度为 O(N*N) 的答案。这不是家庭作业问题。我已经尝试了很多，但无法找到合适的解决方案，并认为我可以在这里得到一些想法。将打印放在一边以考虑复杂性

我的粗略想法是可以动态消除遍历的元素数量，将它们限制在 2N 左右。但我无法得到一个正确的想法。

假设对于各种输入字符串，算法生成具有相同数量的 0 和 1 的二进制字符串。两个不同输入字符串的输出可能相同也可能不同。我们能谈谈算法的空间复杂度吗？

大家好：我阅读了下面的算法来找到二叉搜索树中两个节点的最低共同祖先。

请注意，上述函数假设 n1 小于 n2。时间复杂度：O(n)空间复杂度：O(1)

这个算法是递归的，我知道在调用递归函数调用时，函数参数和其他相关寄存器被压入堆栈，所以需要额外的空间，另一方面，递归深度与大小或高度有关树，比如说n，是O（n）更有意义吗？

感谢您在这里的任何解释！

堆栈溢出。我在这里看到了一些关于时间复杂度的重要资源，但到目前为止，我还无法使用它们来回答这个空间复杂度问题。所以：

如果我将前 n 个素数相乘，存储答案需要什么空间？例如，将前一千个素数相乘并存储结果数（一个整数，尽管很大）。它需要 n 平方或 log(n) 空间吗？

非常感谢！

我有一个问题：

"S"我有一个包含对象的数组n。每个对象也有m字段。我想将其中一些保存在另一个数组中，例如"Q". 我想知道这个简单方法的空间复杂度是O(|Q|)？

将一般树转换为二叉树的时间和空间复杂度是多少？！

谢谢

使用布隆过滤器，我们将获得空间优化。cassandra 框架也有一个布隆过滤器的实现。但具体来说，这个空间优化是如何实现的呢？