标签: space-complexity

就地复杂度和空间复杂度 O(1) 意味着不同的事情吗？如果是，有人可以解释其中的区别吗？

我是一个“空间复杂性”新手，遇到了一个问题。

假设我有一个任意整数的数组：
[1,0,4,2,1,0,5]

我如何重新排序该数组以使所有零都在一端：
[1,4,2,1,5,0,0]

...并计算非零整数的计数（在本例中：5）？

...在O(n)运行时具有O(1)空间复杂度？

我不擅长这个。
我的背景更多是环境工程而不是计算机科学，所以我通常会进行抽象思考。

我想我可以进行排序，然后计算非零整数。
然后我想当我重新排列数组时，我只能做一个每个元素的复制。
然后我想到了类似冒泡排序的方法，交换相邻元素，直到到达零的末尾。
我认为我可以通过移位数组成员的地址来节省“空间复杂度”，因为数组点指向数组，并带有其成员的偏移量。

我要么以牺牲空间复杂度为代价来增强运行时间，要么反之亦然。

解决办法是什么？

将for循环N次循环的变量声明为空间复杂度O(N),即使每次循环重复时这些变量都超出范围吗？

for(var i = 0; i < N; i++){
  var num = i + 5;
}

我编写了不同的 python 代码来反转给定的字符串。但是，无法弄清楚其中哪一个是有效的。有人可以使用时间和空间复杂度指出这些算法之间的差异吗？

def reverse_1(s):
      result = ""
      for i in s : 
          result = i + result
      return result

def reverse_2(s): 
      return s[::-1]

有已经有一些解决方案在那里，但我无法找出时间和空间复杂度。我想知道需要多少空间s[::-1]？

我一直想知道二叉树的迭代前序遍历（使用堆栈）的空间复杂度是多少。我参考了 Elements of Programming Interviews，他们说

空间复杂度为 O(h)，其中 h 是树的高度，因为除了栈顶之外，栈中的节点对应于从根开始的路径上节点的右孩子.

以下是参考代码：

struct Node{
   int data;
   struct Node* left, right;
}
void printPreOrder(struct Node* root){
  if(!root)
   return ;
  stack<struct Node* > s;
  s.push(root);
  while(!s.empty()){
     struct Node *root_element = s.top();
     cout<<root_element->data<<" ";
     s.pop();
      if(root_element->right){
         s.push(root_element->right);
      }
      if(root_element->left){
         s.push(root_element->left);
      }
     }
     cout<<endl;
  }
  return ;
}

我的直觉

在执行算法时，我观察到堆栈中任何实例的最大条目数可以是 max(num_of_leaves_in_left_subtree+1, num_of_trees_in_right_subtree)。由此我们可以推断，对于高度为 h 的树，最大叶子数可以是 2^h。因此，左子树中的最大树数为 2^(h-1)。因此，堆栈中的最大条目数为 2^(h-1)+1。因此，根据我的说法，上述算法的空间复杂度为 O(2^(log(n)))。

有这个问题要求返回数组元素的所有唯一三元组，这些元素加起来为零（交换三元组中两个元素的位置不算作唯一）。

我想出了以下代码：

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // skipping duplicates
    if (i !== 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const s = nums[i] + nums[left] + nums[right];
      // too small; move to the right
      if (s < 0) left++;
      // too big; move …

通过比较运行算法所需的时间与输入的大小，在 Python 中计算时间复杂度非常容易。我们可以这样做：

import time

start = time.time()
<Run the algorithm on input_n (input of size n)>
end = time.time()
time_n = end - start

通过绘制time_nvs input_n，我们可以观察时间复杂度是否为常数、线性、指数等。

是否有类似的经验性编程方法来计算 Python 中算法的空间复杂度，我们可以在其中测量随着输入大小的增长而使用的空间量？

上页。《破解编码面试》第 44 章有以下算法：

int f(int n) {
    if (n <= 1) {
        return 1;
    }
    return f(n - 1) + f(n - 1);
}

书上说它的时间复杂度为 O(2^n) ，空间复杂度为 O(n) 。我得到了时间复杂度部分，因为创建了 O(2^n) 个节点。我不明白为什么空间复杂度不是这样。书上说因为这是因为在任何给定时间只存在 O(n) 个节点。

怎么可能？当我们处于 f(1) 的底层时，调用堆栈不会包含所有 2^n 次调用吗？我缺少什么？

如果我可以提供更多详细信息，请告诉我。

谢谢，

我听说过一类数据结构，称为简洁等级数据结构。这些数据结构有什么作用呢？这里的“简洁”是什么意思？它们是如何工作的？

=SUM(SEQUENCE(10000000))

上面的公式最多可以对 1000 万个虚拟数组元素进行求和。根据这个问答我们知道1000万是极限。现在，如果使用 Lambda 辅助函数将其实现为 Lambda REDUCE：

=REDUCE(,SEQUENCE(10000000),LAMBDA(a,c,a+c))

我们得到，

尝试计算此公式时已达到计算限制

官方文档说

这可能在两种情况下发生：

• 公式的计算时间太长。
• 它使用了太多内存。

要解决此问题，请使用更简单的公式来降低复杂性。

所以，它说原因是空间和时间复杂性。但是抛出这个错误的确切空间是多少呢？这是如何确定的？

在REDUCE上面的函数中，虚拟数组的限制约为 66k：

=REDUCE(,SEQUENCE(66660),LAMBDA(a,c,a+c))

但是，如果我们删除添加条件并使其仅返回当前值c，则允许的虚拟数组大小似乎会增加到 190k：

=REDUCE(,SEQUENCE(190000),LAMBDA(a,c,c))

之后它会抛出一个错误。那么，这里的内存限制是由哪些因素决定的呢？我认为这是内存限制，因为它几乎在几秒钟内抛出错误。