数组复制算法的最坏情况Θ空间复杂度求解

若算法输入为大小为n的数组A，需将其复制到另一个数组B。请问该算法的最坏情况空间效率用Θ表示法应如何表示？我认为最坏情况的大O表示法为O(nlogM)，其中n是数组A的元素个数，logM是最大整数占用的比特空间，但无法确定Θ表示法的形式。我猜想应该是：Θ(Σ₁ⁿ lognᵢ)，其中lognᵢ是数组A第i个索引处整数占用的空间。

核心结论 #

你猜想的Θ(Σ₁ⁿ lognᵢ)是准确的，具体分析如下：

1. 空间维度的定义
   复制数组的场景下，空间效率通常分两种维度：

   • 总空间：包含输入数组A和输出数组B的总占用空间。此时总空间为原数组空间加复制数组空间，即Σ₁ⁿ lognᵢ + Σ₁ⁿ lognᵢ，量级上等价于Θ(Σ₁ⁿ lognᵢ)。
   • 额外空间：算法执行时除输入外新增的空间（也就是存储数组B的空间），直接就是Θ(Σ₁ⁿ lognᵢ)。

2. 与O(nlogM)的关系
   你提到的O(nlogM)是一种特例：当数组中所有元素都是最大整数M时，每个元素的占用空间都是logM，此时Σ₁ⁿ lognᵢ = nlogM，对应的Θ表示就是Θ(nlogM)。但这个表示只适用于所有元素大小一致的场景，而Θ(Σ₁ⁿ lognᵢ)是更通用的形式，能覆盖数组元素大小不均的最坏情况（比如每个元素都取自身类型的最大占用空间）。

内容的提问来源于stack exchange，提问作者ThetaN