计算C程序的空间复杂度

Question

我想计算Windows上C程序的空间复杂度~内存使用量。我想在不查看任务管理器的情况下完成所有这些工作。我发现链接计算代码的空间：

#include <stdio.h> 

int main(void) { 
  int x; 
  for(; scanf("%d",&x) > 0 && x != 42; printf("%d\n", x)); 
  return 0; 
}

成为1724 kB

1. 是如何计算的？
2. 如何实现计算代码段空间复杂性度量的任何系统？

欢迎你的回答。

Answer 1

安吉，从你的回复到沃里克，很明显这里有些混乱。这里的空间复杂性一词可能意味着许多不同的事情，从代码可执行文件的更小的大小，到分配给进程的资源的数量，以及这些资源的数量在执行过程中如何变化。

1724年可以根据其所代表的情况以多种不同的方式计算。它是表示结果可执行文件中的所有内容，还是只表示“代码”文本？在不同的平台上，可执行文件的大小不同重要吗？这只涉及静态信息。动态信息(有关程序运行时性能的信息)是另一种蠕虫。

在这种情况下，您必须认识到，分配给流程的资源可能与流程所需的最低资源不完全匹配。如果您要求一个程序寻找需要分配给进程的最小内存大小，那么您将陷入非常模糊的境地:您是从进程的角度来讨论所需的物理内存还是虚拟内存？例如，如果我们运行同一个进程的两个实例，那么两个进程可以共享只读(例如代码内存)，因此其中一个实例不需要对其进行计算。要求操作系统进行这样的计算是有问题的，因为它需要非常精确地知道您所要求的是什么，而拥有一个通过查看代码文本和忽略平台来计算运行时内存使用量的程序也是有问题的。

计算这个最小值是非常重要的，尽管它可能已经被某些人完成了。无论哪种方式，您都需要使用比“空间复杂性”更具体和更容易混淆的术语来搜索它，这是一种更适用于笔和纸算法的方法。