阵列初始化的时间复杂度是多少？

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;
}

他们俩都花时间吗？案例1的复杂性是什么？哪个更好？

Answer 1

从理论上讲,两者都具有相同的时间复杂度:O(N),N数组的大小在哪里.

但是,第一种方法应该更好,因为编译器可以选择尽可能快地进行初始化(例如,可以通过它完成memset).对于优化,编译器通常比程序员更好.

顺便说一句,如果你的数组有静态存储持续时间(例如,如果你将它声明为全局变量),它将自动初始化为0.

Answer 2

在数组具有静态持续时间(全局变量)的情况下,我会说第一个是非常优选的,因为它不需要任何代码 - 它由运行时环境初始化.

如果变量是自动持续时间(局部变量),哪一个更好,哪一个比另一个好,取决于编译器.最有可能的是,两者都非常相似.

对于所有情况,自动存储持续时间变量的复杂度为O(n).第一种情况是O(1)表示静态存储持续时间变量.

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

您可能还会发现使用memset(array, 0, sizeof(array));优于两者 - 再次,取决于编译器.这仍然是O(n),但是填充数组所花费的实际时间可能更短,因为memset可能比编译器为循环情况[以及它对初始化变量的作用]更好地进行优化.memset不能用于填充数组5.

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

最后,我应该指出,如果这些事情在代码中执行很多,那么这些事情才真正重要.这是一段很长的时间,因为填充40KB的数据需要花费足够长的时间来真正担心它自己.喜欢20多年.