问题标签 [space-complexity]

在许多系统中，head.reverse需要与列表大小成比例的空间，而last需要恒定空间。

是否有系统来执行这样的转变？同样对于reverse.take n.reverse?

编辑：我想扩展我的问题：我不是在进行具体的改造——我更愿意为此进行任何优化。

我需要计算我的公司在存储方面的平均每日增长，但我有疑问，正确的方法是什么？很抱歉使用谷歌翻译。=)

存储空间：

我在 PHP 中的代码：

我的结果是： -5194.6666666667，是不是错了？

假设 n 条记录的键在 1 到 k 的范围内。

• 编写一个算法，在 O(n+k) 时间内对记录进行排序。
• 您可以在输入数组之外使用 O(k) 存储。
• 你的算法稳定吗？

如果我们使用计数排序，我们可以在 O(n+k) 时间内完成，并且稳定但不到位。
如果 k=2，它可以就地完成，但它不稳定（使用两个变量来维护数组中 k=0 和 k=1 的索引）
但是对于 k>2，我想不出任何好的算法

传统的 B 树实现具有 O(n) 空间复杂度 [ 1 ]。

所以假设在一个数据库中（不管实现，只考虑一般情况），我有一个 10GB 数据的表，目前索引大小是 1GB，那么我可以假设如果数据库增长到 100GB，我的索引大小将是 10GB？

尽可能优化（降低空间和时间复杂度）这个功能。

我正在做这个特殊的问题AIBOHP并使用了 dp 方法，该方法基于检查从 1 开始的长度为 i 的子串的末端。虽然我的时间复杂度在 O(n^2) 时很好，但空间占用太多，因此我如果我动态地声明它，我会得到 RTE，或者如果我将它声明为需要减少的全局静态，因为 dp 大小可以是 6100*6100 ，我会得到 RTE。任何建议如何为此目的优化我的以下代码。

问题陈述是：

我的代码是：

python中这个阶乘函数的空间复杂度应该是多少？

在其他语言（如 C）中，同样的想法会导致 O(1) 空间复杂度，但对于这个例子，range(2,n+1) 会导致 O(n) 空间复杂度的空间复杂度吗？

这是水平顺序遍历的代码：

在我看来，空间复杂度应该是 O(2^h)，其中 h 是树的高度，仅仅是因为这是队列在执行期间可以达到的最大大小。在互联网上，我发现空间复杂度为 O (n)。这对我来说听起来不正确。请分享您的意见。

谢谢，

n假设我有一个递归函数，它在具有节点和高度的完美平衡二叉树上工作，log(n)并在树的根部调用下面的函数。

让数组为长度log(n)（它将沿树的路径存储值）。我知道递归调用堆栈将是 max height log(n)。我不确定的是 Java 的“按值传递”性质和 Java 垃圾收集如何影响时间和空间复杂性。

1）将数组传递给递归调用的时间复杂度是多少？如果 Java 是“按值传递”，是否每次递归调用都需要O(log(n))在开始执行任何函数之前简单地复制数组？

2）任何时候这些数组副本中有多少在内存中浮动的上限是多少？我倾向于说O(log(n))。这是否意味着空间复杂度是O(log(n)log(n))？我在一本书中读到“空间复杂度是O(log(n))因为算法将递归O(log(n))时间，并且路径参数在递归期间仅在O(log(n))空间分配一次”。