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

Question

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

情况1：

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

案例二：

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

他们都需要同样的时间吗？案例 1 的复杂性是多少？并且，哪个更好？

Answer 1

理论上，两者具有相同的时间复杂度：O(N)，N数组的大小在哪里。

但是，第一种方法应该更好，因为由编译器选择如何尽可能快地初始化（例如，可以通过 来完成memset）。对于优化，编译器通常比程序员更好。

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

Answer 2

在数组具有静态持续时间（全局变量）的情况下，我会说第一个更可取，因为它不需要任何代码 - 它由运行时环境初始化。

如果变量是自动持续时间的（局部变量），则哪个更好，如果哪个更好，则取决于编译器。最有可能的是，两者都非常相似。

对于所有情况，自动存储持续时间变量的复杂性都是 O(n)。对于静态存储持续时间变量，第一种情况是 O(1)。

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

您可能还会发现 usingmemset(array, 0, sizeof(array));比两者都好 - 再次取决于编译器。这仍然是 O(n)，但是填充数组所需的实际时间可能会更短，因为memset可能比编译器为您的循环案例生成的优化更好[以及它对初始化变量的作用]。memset也不适用于填充数组5。

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

最后，我应该指出，这些事情只有在它们在执行大量代码的情况下才真正重要。自从填充 40KB 的数据需要足够长的时间来真正担心自己已​​经过去了很长时间。像20多年。