问题标签 [space-complexity]

我一直在阅读就地排序算法来对链表进行排序。根据维基百科

合并排序通常是对链表进行排序的最佳选择：在这种情况下，实现合并排序相对容易，它只需要Θ(1)额外的空间，而链表的缓慢随机访问性能使得其他一些算法（例如快速排序）表现不佳，而其他算法（例如堆排序）则完全不可能。

据我所知，归并排序算法不是就地排序算法，并且具有O(n)辅助的最坏情况空间复杂度。现在，考虑到这一点，我无法确定是否存在合适的算法来对具有O(1)辅助空间的单链表进行排序。

从我在维基百科对快速排序空间复杂度的解释中了解到，快速排序的空间复杂度来自于它的递归性质。我很好奇是否有可能以非递归方式实现快速排序，并且在这样做的过程中，以恒定的空间复杂度实现它。

我正在实现一个程序来对可能不适合内存的大文件进行排序。所有文件都将按行排序，因此我正在考虑使用 List 来执行此操作。

我已经计算了内存中有多少行可以将文件拆分为较小的文件，但我不知道内存中需要多少空间来对 N 个元素的列表进行排序。

问题是，知道元素的最大数量（已知大小的字符串）和可用内存，List.Sort 方法需要多少内存空间？

最初的问题陈述是这样的：

给定一个 32 位无符号整数数组，其中每个数字都恰好出现两次，除了其中三个（恰好出现一次），使用 O(1) 额外空间在 O(n) 时间内找到这三个数字。输入数组是只读的。如果有 k 个异常而不是 3 个呢？

如果由于输入限制而接受一个非常高的常数因子，则很容易在Ο(1)时间和空间上解决这个问题（数组最多可以有 2 ³³个条目）：Ο(1)

所以，为了这个问题，让我们放弃对位长度的限制，专注于数字最多可以有m位的更普遍的问题。

概括 k = 2 的算法，我想到的是以下内容：

1. XOR 那些具有最低有效位的数字1和那些分别具有的数字0。如果对于两个分区，结果值都不为零，我们知道我们已经将不重复的数字分成了两组，每组至少有一个成员
2. 对于这些组中的每一个，尝试通过检查第二低有效位来进一步划分它，依此类推

不过，有一个特殊情况需要考虑。如果在划分一个组之后，其中一个组的 XOR 值都为零，我们不知道得到的子组之一是否为空。在这种情况下，我的算法只是忽略了这一位并继续下一个，这是不正确的，例如它对 input 失败[0,1,2,3,4,5,6]。

现在我的想法是不仅要计算元素的 XOR，还要计算应用某个函数后的值的 XOR（我在f(x) = 3x + 1这里选择了）。有关此附加检查的反例，请参见下面 Evgeny 的回答。

现在虽然下面的算法对于 k >= 7 是不正确的，我仍然在这里包含实现给你一个想法：

根据我的分析，这段代码的最坏情况时间复杂度O(k * m² * n)是n输入元素的数量（异或是O(m)，最多k分区操作可以成功）和空间复杂度O(m²)（因为m最大递归深度和临时数字可以是长度m）。

问题当然是是否存在具有良好渐近运行时的正确k << n、有效的方法（为了完整起见，我们假设m << n这里），它也需要很少的额外空间（例如，对输入进行排序的方法将不被接受，因为我们至少需要O(n)额外的空间，因为我们不能修改输入！）。

编辑：既然上面的算法被证明是不正确的，当然很高兴看到它是如何正确的，可能会降低它的效率。空间复杂度应该是 in o(n*m)（即，在输入比特的总数中是次线性的）。如果这样可以使任务更容易，则可以将其k作为附加输入。

我的算法如下图所示。它对服务器进行远程调用并获取结果处理它们，然后再次将远程调用发送到系统。你能告诉我这个算法的时间和空间复杂度是多少吗？

我一直在申请工作，每次听到有关算法时间/空间复杂性的问题时，我都会畏缩和跌跌撞撞。无论我读了多少书，我的大脑似乎都被编程为无法获得任何东西，我认为原因是因为逃学导致我的数学背景非常低。这可能不是常见的 SO 问题，甚至可能由于从根本上讲数学而被删除，但至少我希望我能弄清楚这个问题接下来要去哪里。

我正在使用水平顺序遍历的概念来生成帕斯卡三角形。

这是代码片段：

完整的代码在这里：

这种方法的优点是它的空间复杂度是 O(N)，其中 N 是行数。

有没有更好的方法来做同样的事情？

redis中排序集和列表在空间上有什么区别？我的猜测是排序集是某种平衡二叉树，而列表是链表。这意味着在我为它们中的每一个编码的三个值之上，键、分数、值，虽然我会将链表的分数和值混合在一起，但开销是链表需要跟踪一个另一个节点，并且二叉树需要跟踪两个，因此使用排序集的空间开销为 O(N)。

如果我的值和分数都是长整数，并且指向其他节点的指针也是长整数，那么在 64 位计算机上，单个节点的空间开销似乎从 3 个长整数变为 4 个长整数，即 33%空间的增加。

这是真的？

给定一个数组，其中每个数字的出现次数为奇数，但出现次数为偶数的数字除外。找到偶数出现的数字。

例如

输出应该是：

以下是约束：

1. 数字不在范围内。
2. 就地进行。
3. 所需的时间复杂度为 O(N)。
4. 数组可能包含负数。
5. 数组未排序。

由于上述限制，我所有的想法都失败了：基于比较的排序、计数排序、BST、散列、蛮力。

我很想知道：XORing 会在这里工作吗？如果是，如何？

在浏览了一些SO 帖子后，我发现埃拉托色尼筛法是生成素数的最佳和最快的方法。

我想生成两个数字之间的质数，比如a和b。

AFAIK，在 Sieve 的方法中，空间复杂度为O(b)。

PS：我写的是Big-O而不是Theta，因为不知道能不能减少空间需求。

我们可以降低埃拉托色尼筛中的空间复杂度吗？