数组初始化的时间复杂度是多少？

Question

考虑C或C++中数组初始化的以下两种情况：

情况1：

int array[10000] = {0}; // All values = 0

情况2：

int array[10000];
for (int i = 0; i < 10000; i++) {
    array[i] = 0;
}

它们需要相同的时间吗？Case 1的复杂度是什么？哪个更好？

- vaibhavatul47

---

这个 array 是静态的还是自动的？ - Mats Petersson

我正在寻找两种情况。 - vaibhavatul47

Answer 1

在理论上，两种方法的时间复杂度都是相同的：O(N)，其中N是数组的大小。

然而，第一种方法应该更好，因为这取决于编译器如何尽快初始化（例如，可以通过memset完成）。对于优化，编译器往往比程序员更好。

顺便说一下，如果您的数组具有静态存储期（例如，如果将其声明为全局变量），它将自动初始化为0。

- md5

---

请参考 C++ 的 std::fill 函数。 - Thomas Matthews

假设使用memset是好的，编译器在第2种情况下同样可以使用memset。 - Bo Persson

@BoPersson：这是正确的，尽管在第二种情况下，编译器似乎更难检测到我们正在尝试做什么。 - md5

Answer 2

对于数组的静态存储期（全局变量）的情况，我认为第一个选项更可取，因为它不需要任何代码 - 它由运行时环境初始化。

如果变量是自动存储期（局部变量），则哪个更好，如果有一个比另一个更好，则取决于编译器。很可能两者都非常相似。

对于所有情况，自动存储期变量的复杂度为O(n)。对于静态存储期变量，第一种情况为O(1)。

当然，如果您想使用值5填充数组，则第二个选项更好，因为它不需要在源文件中写入10000个5。

您还可以发现，使用memset(array, 0, sizeof(array));比两者都要好 - 再次取决于编译器。这仍然是O(n)，但是填充数组所需的实际时间可能更短，因为memset可能比编译器为您的循环情况生成的内容以及已初始化变量生成的内容更好地优化了。 memset也无法用于用5填充数组。

您还可以使用std::fill(array, &array[10000], 5);将值5设置为整个数组中的所有值，编译器将应该能够很好地优化它。

最后，我应该指出，这些事情只在执行很多的代码中真正重要。填充40KB的数据需要很长时间才能真正担心它本身。像20多年那样。

- Mats Petersson

---

gcc有时会出现未完全展开循环的情况。例如，您使用小常量大小调用memset，并看到它被转换为一系列存储--您可能认为这是内联后跟随loop unrolling 如 -funroll-loops，但实际上这是由于神奇的intrinsic memset所造成。 - Steve Jessop

第一个情况是对于静态存储期变量的O(1)。无论在何处运行，都不能在常数时间内执行初始化。您需要从内存中删除位。无论是您的程序运行时间还是操作系统都不重要。 - lejlot

@lejlot：内存需要由操作系统（或加载器，或您称之为什么）分配。在大多数操作系统中，它会自动填充为零。因此，在创建空间之外，操作系统/加载器将不需要执行任何操作。在编译器的上下文中，没有填充的必要。它只是将变量放入.bss中，并以填充了零的形式出现。当然，某些东西需要分配空间，并且需要用SOMETHING来填充 - 但是假设操作系统使用零进行填充，则对于静态分配的数组使用= {0}不会增加额外的时间。 - Mats Petersson

我的唯一观点是，在你所提到的渐进复杂度意义上，操作系统用零填充（O(n)）和手动填充（O(n)）之间没有区别。显然，操作系统会更快地完成这个任务，但这不是我的重点。 - lejlot

我并不是说操作系统会更快，我是说“当你分配内存时，你可以免费获得它”。你不能获得未清零的内存。我向你挑战，展示给我看，不初始化为零（对于静态持续时间变量）在任何方面都比初始化更快。当然，清除内存需要时间。但是，将代码/数据加载到内存中时，这是“免费”的。 - Mats Petersson