循环中最糟糕的空间复杂性，它创建每个迭代
无论是使用的算法总量的总和，还是仅在关键时间（最糟糕的时）消耗的空间，我都在努力找到适当的最差空间复杂性定义。
例如：
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）。
I am struggling to find a proper definition of worst space complexity whether it is the sum of the total amount of the algorithm used or if it is only the space consumed by the algorithm at a critical time, the worst one.
As an example:
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);
}
}
For the first definition it is roughly O(N²) and for the second one O(N).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
它将是
o（n）。分配完成后，您将明确释放内存。我同意malloc的内部工作原理是有用的，但是假设正常实现不足以更改空间复杂性（用于跟踪o（o（n））内存分配它保留o（n^2）元数据的数量 - 只是一个奇怪的例子）。一个有趣的观点，可以清除您的想法。如果您评论此
免费（..）行，则空间复杂性将为o（n^2）。这就是所谓的内存泄漏。It would be
O(n). You are explicitly freeing up the memory after the assignment is done. I agree the inner workings of themallocwould be useful but assuming a normal implementation which doesn't use memory enough to change the space complexity ( For trackingO(n)memory allocation it keepsO(n^2)amounts of metadata - just a weird example).An interesting point, to clear up your idea. If you comment out this
free(..)line, then the space complexity would beO(n^2). This is what is known as memory leakage.