c - 初始化数组填零的运行时

Question

如果我要使用堆栈上的零填充初始化语法定义以下数组：

int arr[ 10 ] = { 0 };

...运行时间是常数还是线性？

我的假设是它是一个线性运行时间——我的假设只是针对calloc必须遍历每个字节以将其填零的事实。

如果您还可以提供原因而不仅仅是订单 xxx，那就太棒了！

Answer 1

运行时在数组大小上是线性的。

要了解原因，这里有一个 memset 的示例实现，它将数组初始化为任意值。在汇编语言级别，这与您的代码中发生的事情没有什么不同。

void *memset(void *dst, int val, size_t count) {
    unsigned char *start = dst;
    for (size_t i = 0; i < count; i++)
        *start++ = value;
    return dst;
}

当然，编译器通常会使用内在函数一次设置多个数组元素。根据数组的大小以及对齐和填充等内容，这可能会使数组长度上的运行时间更像一个楼梯，步长基于向量长度。由于数组大小的微小差异，这将有效地使运行时保持不变，但一般模式仍然是线性的。

Answer 2

这实际上是冰山问题的一角。您真正要问的是初始化数组的顺序（Big Oh）是什么。本质上，代码循环遍历数组的每个元素并将它们设置为零。你可以编写一个 for 循环来做同样的事情。

该循环的数量级是 O(n)，也就是说，循环所花费的时间与被初始化的元素数量成正比。

如果硬件支持一条指令，该指令将位置 X 到 Y 的所有字节设置为零，并且该指令在 M 个指令周期内工作，并且无论将字节数设置为零，M 都不会改变，那么这将是顺序 k，或 O(k)。

通常，O(k) 可能被称为常数时间，而 O(n) 可能被称为线性。