algorithm - 复制数据结构和空间复杂度

Question

我经常被要求编写函数，这些函数采用某种类型的参数(例如字符串)并以某种方式对其进行操作，如果它是其他数据结构，就会容易得多。我可以将一个字符串转换为字符数组并将字符串设置为空，同时考虑我的函数占用 O(1) 空间，或者即使我立即删除另一个副本，复制所有元素是否使其成为 O(N)？我以字符串为例，因为它们是不可变的。在另一种情况下，我会在将数据添加到另一个结构时尝试从一个结构中删除数据。

这里我只是使用 String 和 char[] 作为例子。一般来说，我想知道复制我的数据是否会降低我的算法的空间复杂度，即使我正在删除另一个副本。

Answer 1

复制会降低您的空间复杂度，因为原件和副本同时在内存中(即使这只是短暂的情况)，因此您需要有额外的可用内存。即使您没有更多可用内存，内存中算法也能够执行。