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

Question

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

案例一:

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

案例二:

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

他们都需要同样的时间吗？情况 1 的复杂性是什么？以及，哪个更好？

Answer 1

如果数组是静态持续时间(全局变量)，我会说第一个更可取，因为它不需要任何代码 - 它由运行时环境初始化。

如果变量是automatic duration(局部变量)，哪个更好，哪个好，哪个好，取决于编译器。最有可能的是，两者将非常相似。

对于所有情况，自动存储持续时间变量的复杂度都是 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 多年。