问题标签 [space-complexity]

我想存储一个制表符分隔值的输入，其中 C1、C2、C3 和 C4 表示数据的列，并且有 N 行数据。如果是这样，我可以在哈希中进行查找以查看 C1、C2、C3、C4 的某些给定值是否存在。有人向我建议，在最坏的情况下，它的空间复杂度是 N ⁴。我想帮助制定一个明确的解释，说明为什么这是不正确的。

我正在尝试制作一个迭代器，该迭代器对特定文件夹中的所有文件和文件夹执行广度优先遍历。我已经用深度优先遍历完成了这个，它返回，例如：

等等

现在我正在尝试制作一个程序，该程序将返回广度优先的结果：（或逐级）

对于相同的层次结构。但是，我遇到了一个绊脚石：假设我希望这些以正确的顺序发生（特别是，不是相反的顺序），我找不到任何方法来执行此操作而最终需要 O(n) 内存，其中n是驱动器上文件/文件夹的数量，因为在我看来，我最终需要将整个驱动器层次结构保留在内存中，而对于 DFS，我可以完全忽略我之前在层次结构中的同一级别。

所以我的问题是：有没有比线性更好的方式来使用内存来遍历文件夹？

你得到一个整数数组。您必须输出最大范围，以便该范围内的所有数字都存在于数组中。这些数字可能以任何顺序出现。例如，假设数组是

在这里，我们找到两个（非平凡的）范围，这些范围中的所有整数都存在于数组中，即 [2,8] 和 [10,12]。其中 [2,8] 是较长的一个。所以我们需要输出它。

当我被问到这个问题时，我被要求在线性时间内做到这一点，并且不使用任何排序。我认为可能有一个基于哈希的解决方案，但我想不出任何东西。

这是我的解决方案尝试：

我被困在这部分......我不知道应该使用多少个 tempanswer[] 数组。

我很难找到我编写的这段代码的空间和时间复杂度，以查找字符串中的回文数。

I gave it a shot and this what i think:
in main we have two while loops. The outer one runs over the entire length-1 of the string. Now here is the confusion, the inner while loop runs over the entire length first, then n-1, then n-2 etc for each iteration of the outer while loop. so does that mean our time complexity will be O(n(n-1)) = O(n^2-n) = O(n^2)? And for the space complexity initially i assign space for string length+1, then (length+1)-1, (length+1)-2 etc. so how can we find space complexity from this? For the checkPalin function its O(n/2).
i am preparing for interviews and would like to understand this concept.
Thank you

是这样声明的数组：
int array[M]，O(1)在空间中还是O(n)？其中 M 是某个固定值。对我来说O(n)是有道理的，因为它不仅仅是一个变量，而是一个完整的数组。但后来我认为这可能是O(1)因为我们有一个固定的大小并且它没有改变！

在大 O 表示法中，Lempel-Ziv-Welch 和 Huffman 压缩算法的空间和时间复杂度是多少？谷歌让我失望了。

谢谢，

弗朗西斯科

Mathematica 的CylindricalDecomposition实现了一种称为圆柱代数分解的算法。Wolfram MathWorld 关于圆柱代数分解的文章称，该算法“对于复杂的不等式在计算上变得不可行”。

这个说法可以更准确吗？具体来说，时间和空间如何与多元多项式的变量的次数和数量相关？时间和空间是否取决于其他参数？

我想到的算法是

• 保持一个大小为 K 的 MaxHeap
• 插入每个元素
• 如果堆已满，则丢弃较小的值
• 最后，Kth max 是 MaxHeap 中较小的一个

这会给我 O(NlogK)。有更好的算法吗？我无法快速选择，因为数组无法存储在内存中。

我在文件中有一行任意长的整数（或浮点值），用逗号分隔：

现在，我必须读取这些值并将它们存储在一个数组中。

我当前的实现如下所示：

我不喜欢这个实现，因为：

• 使用ifstream整个文件被加载到内存中，然后被克隆到一个float []
• 有不必要的重复（从std::stringto转换const char*）

有哪些方法可以优化内存利用率？

谢谢！

在自上而下的合并排序中，递归函数以这种方式调用：

教科书中给出了该策略的空间复杂度为 O(n)。而如果我们仔细观察递归：我们在递归调用中传递指向数组的指针。其次，通过将底部节点合并到父节点，以遍历的前序顺序解决递归。所以每次堆栈上都有 O(logn) 个变量（或堆栈上的 O(log n) 个帧）。那么，尽管有就地合并技术，空间复杂度如何为 O(n)？