在每次迭代中创建数组的循环的最差 space 复杂度是多少

Question

我正在努力寻找最差 space 复杂度的正确定义，无论它是所用算法总量的总和，还是仅是算法消耗的 space关键时候，最坏的时候。

举个例子：

void myFunc(n) {
  for(int j = 0; j < n ; ++j) {
     int* myTab = malloc(n*sizeof(int));
     for(int i = 0; i < n; ++i) {
        myTab[i] = 1;
     }
      free(myTab);
   }
}

第一个定义大致为 O(N²)，第二个定义为 O(N)。

Answer 1

应该是O(n)。分配完成后，您将明确释放内存。我同意 malloc 的内部工作原理是有用的，但假设一个正常的实现不会使用足够的内存来改变 space 复杂性（为了跟踪 O(n) 内存分配它保持 O(n^2) 大量的元数据 - 只是一个奇怪的例子）。

一个有趣的观点，澄清你的想法。如果注释掉此 free(..) 行，则 space 复杂度将为 O(n^2)。这就是所谓的内存泄漏。

在每次迭代中创建数组的循环的最差 space 复杂度是多少

What's the worst space complexity of a loop which create an arrayat each iteration

c

algorithm

space-complexity