arrays初始化的时间复杂度是多少?

考虑以下两种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的复杂性是什么? 哪个更好?

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

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

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

从理论上讲,两者都具有相同的时间复杂度: O(N) ,其中N是数组的大小。

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

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