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

Question

通常阅读一些内容时，我想到了这个问题。如果我有一个像下面这样的字符数组初始化，那么这个语句的时间复杂度是多少？

char array[] = {'a','b','c','d','e'};

它是否真的会执行5次以赋值每个变量，就像我们在循环中做的一样。如果这个假设是正确的，为什么会这样呢？

- dicaprio

---

我会假设任何非白痴编译器都可以使用不超过5个赋值语句处理5个不同的内存位置，时间复杂度为O(n)。如果决定进行矢量化，可能还可以更少。 - Mysticial

如果数组与您的示例相同，编译器将只将数组值作为连续的内存块放置在应用程序数据段中，并让array指向它。没有任何初始化或循环。 - Some programmer dude

如果 array 在栈上，就需要在本地初始化。但标准中没有规定编译器应该如何处理，所以这个问题实际上无法回答——请检查编译器的输出。GCC 在此处执行 5 字节移动。 - Mat

Answer 1

根据声明的位置和编译器的智能程度，时间复杂度可能是O(1)或者O(n)。以下是一些情况:

1. 全局声明, 如果编译器比较聪明，会将其放入数据段，并初始化，因此是O(1)
2. 本地声明, 如果经过聪明的编译器证明只读，就像上面一样，加上对数组的引用赋值，仍然是O(1)
3. 本地声明, 读写, 可以是存储分配+5次赋值 (显然是O(n)) 或者存储分配+数组数据复制 （像2那样，但是数据被复制而不是仅有引用）。如果使用向量化代码，后者可以是O(1)，（嗯...或多或少，因为这取决于很多因素）

- LeleDumbo

---

对于第二点，我认为必须有更多的要求。编译器还需要能够证明永远不会比较数组的基地址。例如来自不同递归调用的“相同”数组的两个实例必须始终被证明是不同的。我所知道的唯一允许这种折叠的情况是const限定的复合字面量。 - Jens Gustedt

@JensGustedt 如果没有 const，可能是必要的。但是一个真正聪明的编译器可以将其视为已声明为 const，无论是否声明为 const。 - LeleDumbo

即使使用了 const，对于两个不同的对象，使用 == 测试它们的地址必须返回 false。相应于两个不同递归调用的同一变量的两个实例满足该要求。 - Jens Gustedt

Answer 2

这是O(N)的。它可能是快速或高效的O(N)。如果它是静态分配的数组，则初始化只会执行一次。

但无论如何，它都是O(N)。

请注意，即使它是一个放置在程序的二进制映像中的数组（因为编译器确定该数组永远不会被修改），初始化它仍然是一个O(N)操作，即使初始化可能发生在程序事件到达main()之前或作为程序图像加载的一部分完成。

它是O(N)，因为执行初始化的任何内容都必须写入数组的每个位置，因此长度比另一个数组长100倍的数组将有大约100倍的操作来完成初始化。

- Michael Burr

---

我不明白你的观点。据我所知，这种静态初始化的值是放置在二进制映像中的。通常，该二进制的那部分会被“mmap”（或类似方式）进行“写时复制”。因此，初始化的开销仅在将值写入特定位置时才会发生。特别地，从未访问的变量根本没有任何开销。按照大O符号表示法，总成本为O(M)，其中M是数组各个位置的访问次数。因此，在大O符号表示法方面，根本没有开销。不过，大O符号中隐藏的常数是页面大小。 - Jens Gustedt

Answer 3

正如其他人所说，它可以在O(n)时间内完成。

但它永远不可能是O(1)！ 你怎么能在更短的时间内写入n个内存位置（无论我们有什么类型的内存）？ O(1)意味着操作不取决于输入的大小。我不想把图灵机带到讨论中，但在运行时期间，上述语句总会有一个O(n)操作。

- UmNyobe

---

不，这个分析太粗糙了。你需要用程序访问数组元素的次数来衡量它，单位为 M。请参见我对 Micheal Burr 回答的评论。 - Jens Gustedt

@用户 - 当字符串很短时，您可以一次写入多个字符。在我的64位机器上，编译器使用单个寄存器一次移动8个字符。 - Bo Persson

@BoPersson 是的，但你一次可以移动的字符数量是有限制的。 - UmNyobe

Answer 4

时间复杂度将简单地为0，而不是O或o(n)。 数组的位置将在程序运行之前设置为起始值。位置和值将在编译阶段准备好，并在链接阶段设置。

没有任何命令来实现所提到的行。也没有时间花费。

- Gangnus