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

Question

在 C 中声明和定义(但不初始化)数组的时间复杂度是多少？答案为何如此？

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

这是一个具有此类数组的程序示例:

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

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

Answer 1

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

我认为许多实现实际上在进入函数时为函数分配了所有空间，而不是调整每个 block 的 SP。但是存在于不重叠的 block 中的变量可能共享堆栈帧中的相同内存。但这与所提出的问题并不真正相关，除非您想知道两者之间是否有区别

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 是数字局部变量。