问题标签 [space-complexity]

有人可以告诉如何生成 n 位字符串（所有可能的组合），即使用分而治之的方法从 0 到 2^n-1 计数位。

我可以使用以下算法做到这一点，但空间复杂度和时间复杂度都是 O(2^n)。有人可以给我一个更好的算法（使用分而治之），它需要比这更少的空间。

我已经实现了以下快速排序算法。网上我读到它有 O(log(n)) 的空间要求。为什么会这样？我没有创建任何额外的数据结构。

是因为我的递归会在堆栈上使用一些额外的空间吗？如果是这种情况，是否可以通过不递归（而不是使其迭代）来减少内存？

我一直在编写一个 Java 程序，使用操作数堆栈和运算符堆栈从中缀表示法转换为前缀表示法。我已经根据此处最佳答案中的伪代码实现了一个工作转换器：

中缀到前缀的转换

但是，我现在正在尝试计算上述算法的时间和空间复杂度。

我认为空间复杂度必须是 O(n)，因为我们只有两个堆栈来存储它们之间共享的输入。

考虑到时间复杂度，我不完全确定，是不是 O(n^2) 因为必须将每个子部分从中缀转换为前缀？我不太确定这部分。

基本上我的问题是：我的空间复杂度结果是否正确，算法的时间复杂度是多少？

非常感谢！

编辑： 这是算法的伪代码：

删除二叉树中所有节点的标准算法使用后序遍历这些节点：

该算法使用 O(h) 辅助存储空间，其中 h 是树的高度，因为在递归调用期间存储堆栈帧所需的空间。但是，它运行时间为 O(n)，因为每个节点都被访问一次。

是否有一种算法可以在不牺牲运行时间的情况下仅使用 O(1) 辅助存储空间来删除​​二叉树中的所有节点？

一般来说，我对分析空间复杂性有点困惑。我不确定“算法占用的额外空间”的含义。什么算作 1 的空间？在这里的例子中

空间复杂度为 O(n)，我猜这是由于数组大小为 n。

但是对于像堆排序这样的东西，它需要 O(1)。就地堆排序是否也需要一个大小为 n 的数组（n 是输入的大小）？还是我们假设输入已经在数组中？为什么堆排序的空间复杂度为 O(1)？

谢谢！

一般来说，更具体地说是伯努利混合模型（又名潜在类分析）。

问题01： 当我测量一个算法的复杂度时，如何找到T(1)？

例如我有这个算法

我怎样才能找到 T(1)？

问题2 ：

这个等式中的“1”是什么意思

亲切地

我刚刚编写了这个合并排序的工作版本：

但是，如果您注意到，我使用 copyOfRange 函数创建一个新数组，该数组是父数组某个部分的副本。java中是否有比这更节省空间的合并排序实现？

一群孩子围成一圈。第一个孩子被选中，他们从那个孩子开始顺时针计数，直到达到一个固定的数字（n，在游戏开始时给出）。当计数达到 n 时，第 n 个位置的孩子被淘汰。游戏从下一个孩子开始再次继续，直到剩下一个孩子。您的目标是打印直到最后一个孩子的位置。

例如，如果有 10 个孩子，固定数 n 为 6，那么最后一个孩子的位置是 3。

有没有更好的编程算法来解决这个问题？

PS 我知道我们可以使用数组或其他数据结构轻松地做到这一点。我只想要最好的策略，最好是数学方法。

我想知道遵循 if 语句的复杂性

VS

并且 isTrue 定义为

我当时在想，复杂性if (isTrue())要低一些，if(isTrue()==true)因为在案例 2 中需要对 equals 进行额外比较。

空间复杂度如何？

有什么不一样的想法吗？