C中数组声明和定义的时间复杂度是多少？

Question

在 C 中声明和定义但不初始化数组的时间复杂度是多少？答案是什么原因？

我对编译和运行时间的时间复杂度感兴趣，但更感兴趣的是运行时间。

下面是一个包含此类数组的程序示例：

int main () 
{
    int n[ 10 ]; /* n is an array of 10 integers */
    return 0;
}

如果不是O(1)，常数时间，有没有一种语言可以在常数时间内声明和定义数组？

Answer 1

语言没有指定这一点。但是在典型的实现中，块中所有局部变量的 space 只需通过在进入该块时根据所有变量的总大小调整堆栈指针来分配，即 O(1)。数组仅包含在该总大小中，并且是在编译时计算的。进入块时不会分配 VLA，分配会延迟到声明的执行（因为它取决于必须首先分配的变量），但它仍然只是调整 SP 寄存器的 O(1) 操作。

我觉得很多实现其实是在进入函数的时候就把一个函数的space都分配了，而不是每块调整SP。但是不重叠的块中存在的变量可能在堆栈帧中共享相同的内存。但这与所问的问题并不相关，除非您想知道

之间是否存在差异

int a[10];
int b[10];
// code that uses a and b

和

int a[10];
{
    int b[10];
    // code that uses a and b
}

每个变量的编译时复杂度为O(1)（只需要查找数据类型的大小，如果是数组则乘以大小），所以O(n)其中n是局部变量的数量。

Answer 2

这是一个奇怪且可能无法回答的问题。通常，复杂性分析和 "big O" 符号应用于算法，而不是实现。但是在这里，您基本上完全是在询问实现，以及分配数组的非算法 "noise" 或 "overhead" 活动。

定义和声明是编译时的概念，我从未听说过 big-O 应用于编译时活动。

在运行时，可能需要做一些工作才能使数组 spring 存在，无论它是否已初始化。如果它是一个本地 ("stack") 数组，OS 可能必须为新函数的堆栈帧分配内存并在内存中分页，这可能或多或少是数组大小的 O(n)。但如果堆栈已经存在，它将是 O(0)，即空闲。

如果数组是静态的 and/or 全局的，另一方面，它只需要分配一次。但是，同样，OS 将不得不为其分配内存，这可能是 O(n)。 OS 可能需要也可能不需要对内存进行分页——取决于您是否对数组进行任何操作，以及 OS 的 VM 算法。（一旦您开始谈论 VM 性能，定义和思考就会变得非常棘手，因为开销最终可能会以各种方式与其他进程共享。）

如果数组是全局的或静态的，如果你不初始化它，C 说它被初始化为 0，这是 C 运行-time library and/or OS以某种方式为您做事，在某种程度上几乎肯定是 O(n) - 尽管它最终可能会以各种复杂或无法衡量的方式与其他活动重叠或共享。

Answer 3

在 C 语言中，在运行时间实例化一个变量（无论是标量还是数组）的成本（通常）低于噪声，尽管它确实取决于底层平台。例如，在 x86 平台上为 auto 变量预留 space 是（通常）通过简单地调整堆栈指针来完成的：

subq    $<em>X</em>, %rsp

其中X是函数中所有局部变量所需的存储量。所以无论X是4还是4K¹，所花的时间都是一样的。

static 变量的存储可以从程序映像本身内部分配，以便在程序加载到内存中后立即预留存储空间 (使其在运行时间有效地实现零成本）。

还是不行。

Big O 表示法在这里并不适用；分配存储的确切机制可能会因实施而异很多，其中大部分是您无法控制的。 Space 通常是这里的限制因素，而不是时间。

^{我们无法控制的模数页面错误或其他内存子系统功能。}

C中数组声明和定义的时间复杂度是多少？

What is the time complexity of array declaration & definition in C?

c

arrays

time-complexity

variable-declaration