我没有找到关于如何选择空数据结构的init时间复杂度的资源。我知道它基于实现和编程语言，但我认为存在约定。例如，已知哈希表的 init 是 O(1)，但看起来 init 空数组（非动态）是 O(n)。
我认为我可以通过基于数组的实现（通过空间和 ADT 操作最有效）来处理它，例如 BST、AVL、堆（可以在 O(n) 中显示），以及基于非数组的实现，例如链接列表、堆栈等（O(1)）。这听起来不太准确，因为如果我们想初始化空的二维数组，时间复杂度是 O(n^2)，这听起来很昂贵。另一个例子是我们可以用哈希表初始化空数组，时间复杂度为 O(1)。我想对此进行澄清。
我不知道正式约定是什么，但实际上分配通常是 O(1)。操作系统可以通过向进程承诺内存，但在进程写入部分内存之前不实际分配硬件资源来进行欺骗。因此从这个意义上说，分配 1 字节或 1 GB 通常是相似的（但是，总是有例外）。
同样，实际的初始化取决于您所说的空的含义。如果为空意味着未初始化，则进程不需要花费任何额外的时间来创建结构。但是，如果您想要将内存设置为某种初始化状态，那么根据您初始化的元素数量，它的复杂度将是 O(n)。请记住，与缓存命中率等其他因素相比，在大多数应用程序中，这个时间通常可以忽略不计。
相反，我建议分解时间复杂度和内存复杂度，以便它们可以单独显示。在这种情况下，时间复杂度不包括分配/初始化时间，仅包括实际算法。内存复杂度与时间复杂度类似，但表示 n 变化时所需总内存的近似值。