2

Say I am given an array, and a function called replace:

void replace(from, to, items[])

whose job is to replace the array elements in the range [from, to) with the elements in items.
I'll assume the maximum size of the array is known beforehand, so I can ensure the array will never overflow.

My question is, if I am given a list of replacements (e.g. elements of the form (from, to, items)), is it possible for me to obtain the final resulting array with a faster time complexity than performing each operation sequentially?

In other words, is there any advantage to knowing the sequence of operations beforehand, or is it no better than being given each operation one by one (in terms of the asymptotic time complexity)?

Note: It seems like the question is confusing; I did not intend to imply that the number of elements replacing a given range is the same as the size of that range! It could be fewer or more, causing shifting, and the point of the question was was to ask if knowing them beforehand could avoid extra work like shifting in the worst case.

4

2 回答 2

1

我认为这可能不是您所发现的，但使用Rope可以缩短时间复杂度。它提供像 concat 这样的字符串操作，而无需“移位”实际数组。（不需要是字符的字符串。任意类型的元素可以用作字母）

根据维基百科（......因为我还没有使用过它），绳索是一个由分段字符串组成的平衡二叉树。一根绳子代表连接所有碎片字符串的长字符串。你的 replace() 函数可以在绳子上使用 Split() 和 Concat() 操作来实现，这两个操作只需要 O(log(n)) 时间。在这里，我把 n 作为绳子代表的长绳的长度。

要获得正常数组，可以使用 Report() 操作在 O(n) 时间内转换绳索。

所以答案是：有一种算法比顺序应用字符串操作更快。

  • 将给定数组转换为绳索
  • 在绳子上应用每一个更换工作。每个操作都在 O(log(n)) 中运行，并且不复制实际的数组项。
  • 将处理后的绳索转换为真正的数组（这会导致所有项目的副本）。
  • 把它返还。
于 2013-04-30T04:53:20.497 回答
0

它总是线性的，一直到memcpy' 水平。加快它的唯一方法是用时间换空间 - 覆盖数组下标运算符，以便在from和to指向元素之间的元素items而不是原始数组，这在任何情况下都不是一个好的解决方案。

于 2013-04-26T01:40:24.397 回答