如何优化N个字符串

如果我们给定的n字符串，其长度和一个附加（字符串S1，S2线）函数，这将字符串连接在一起S2与S1和S3返回的级联的成本。我们如何优化将所有这些字符串连接成一个大字符串的成本。如何优化N个字符串

如果没有给出这样的功能，我们可以简单地创建一个大小为（N1 + N2 + ... NN）的输出字符串，并保持追加到它的每个字符串的字符。但是，使用此函数时，我们必须遍历输入字符串s1以查找它的结尾，然后开始将字符串s2连接到它。

所以如果字符串的长度是2，6，1，3，4 ..

add (s1, s2) traversal for length 2, op string of length 8 
add (s1, s3) traversal for length (2+6) op string of length 9 
add (s1, s4) traversal for length (2+6+1) op string of length 12 
add (s1, s5) traversal for length (2+6+1+3) op string of length 16...and so on..

来源

2012-10-11 user1071840

你可以提供一个更精确定义你认为add（）操作的“成本”是什么？ – rici

我举了一个例子，这里的成本是指我必须遍历整个字符串的次数，并且遍历大小根据输入字符串的大小而增长。 – user1071840

"with this function given we'd have to traverse input string s1 
to find it's end and then start concatenating string s2 to it. "

您可以通过Concat的字符字符串的字符权当你穿越它。将一个小字符串附加到结果字符串后，可以获得指向结果字符串结尾的指针。因此，在添加下一个小字符串时，请使用该字符串，以便您不必一直遍历到该位置。

来源

2012-10-11 04:59:00

Thera是这样做的两种方式。

对数组进行排序，然后保持连接，这样会降低成本。

时间复杂度O（nlogn）其中n是阵列的尺寸。（假如你有使用快速排序）空间复杂度为O（LOGN）
创建array.Now的最小堆从堆中取出1日2分钟，加入他们
并添加再次堆，需要多少时间？

创建最小堆需要O（N）。删除第一个和第二个Min将采取O（n）+ O（n），等待如何？，用最后一个元素替换root并调用heapify，则需要O（logn），因此不会删除。现在，我们要做同样的事情
其余的n-2个元素，因此将采取总O（N-2（LOGN））那是最糟糕的，添加两个元素需要O（1）和插回，并再次调整堆会取O（logn）总的来说它是O（nlogn）的顺序，我们也可以在这种情况下看到更多的呼叫和指令需要。

整个问题只是需要排序的数组，我们可以将成本最小化级联，但如果我们需要更多地考虑选择合适的排序算法，如果我们考虑的时间安空间

来源

2013-09-05 07:26:59 pyshcoguy

其实OP提出的问题并不清楚，因此目前还不清楚这个答案试图达到什么目的。 – justhalf

@justhalf，问题提出以最小化连接两个字符串的成本，让我们的例子1,5,2是给定的字符串的长度在阵列（未排序，追加按顺序） 1 + 5 = 6 6 + 2 = 8 总成本= 14您可以优化总成本吗？是的，如果对这个数组进行排序，它会是1 2 5，然后追加1 + 2 = 3，然后3 + 5 = 8，因此总成本将为11，因此排序是实现优化的一种方式。 – pyshcoguy

如何优化N个字符串

回答

相关问题