复制数据结构和空间复杂性

我经常被要求编写采用某种类型的参数（如字符串）的函数，并以某种方式操纵它，如果它是某种其他数据结构，那将更容易。我是否可以将字符串转换为字符数组，并将字符串设置为空，同时考虑我的函数使用O（1）空间，还是复制所有元素使其成为O（N），即使我立即删除另一个副本？我使用Strings作为例子，因为它们是不可变的。在另一种情况下，我会尝试从一个结构中删除数据，并将其添加到另一个结构中。复制数据结构和空间复杂性

我只是使用String和char []作为示例。一般来说，我想知道如果复制我的数据，即使我删除了其他副本，也会减少算法的空间复杂性。

来源

2014-10-11 user137717

由于原件和拷贝同时在内存中（即使这只是简单的情况），拷贝会减少空间复杂性，所以您需要拥有可用的额外内存。即使您没有更多可用内存，内存中算法也可以执行。

来源

2014-10-11 00:16:43

我是否认为我的函数只需要O（1）空间，如果我可以从一个结构中删除，因为我建立了另一个结构？就像我可以在从堆栈中删除时添加到数组列表一样？ – user137717 2014-10-11 01:19:22

@ user137717这是正确的，假设你有一个恒定大小的数组列表缓冲区（相对于当前大小的某个百分比的缓冲区） – 2014-10-11 01:43:17

@ user137717我需要修改该评论 - 当数组列表被调整大小时通常需要执行另一个副本（例如，你有一个数组列表大小'n'，你分配一个新的数组列表大小'n' + 10，将旧数组复制到新数组，并且释放旧数组），这意味着该副本将需要线性空间。为了它需要恒定的空间，你需要将其复制到分块列表（数组链表）中。请注意，像C这样的语言可能允许使用'realloc'调整原地数组大小（虽然这取决于'realloc'实现） – 2014-10-11 05:13:23

复制数据结构和空间复杂性

回答

相关问题