解决方案的复杂性分析，以最大程度地降低连带成本

这是关于分析热门面试问题的解决方案的复杂性。

问题

有一个concat(str1, str2)连接两个字符串的函数。函数的成本由两个输入字符串的长度来衡量len(str1) + len(str2)。实现concat_all(strs)仅使用concat(str1, str2)函数连接字符串列表的实现。目标是使总的连接成本最小化。

警告事项

通常在实践中，对于在循环中连接成对的字符串会非常谨慎。在这里和这里可以找到一些很好的解释。实际上，我亲眼目睹了由此类代码引起的严重性为1的事故。除了警告，我们可以说这是一个面试问题。对我来说真正有趣的是围绕各种解决方案的复杂性分析。

如果您想考虑这个问题，可以在这里暂停。我将在下面介绍一些解决方案。

解决方案

1. 天真的解决方案。遍历列表并连接 def concat_all(strs): result = '' for str in strs: result = concat(result, str) return result
2. 最小堆解决方案。这个想法是首先连接较短的字符串。根据字符串的长度，保持字符串的最小堆。每个串联从最小堆连接2个字符串，并将结果推回最小堆。直到在堆上只剩下一个字符串为止。 def concat_all(strs): heap = MinHeap(strs, key_func=len) while len(heap) > 1: str1 = heap.pop() str2 = heap.pop() heap.push(concat(str1, str2)) return heap.pop()
3. 二进制连接。可能不直观。但是另一个好的解决方案是将列表递归地分成两半并进行连接。 def concat_all(strs): if len(strs) == 1: return strs[0] if len(strs) == 2: return concat(strs[0], strs[1]) mid = len(strs) // 2 str1 = concat_all(strs[:mid]) str2 = concat_all(strs[mid:]) return concat(str1, str2)

复杂

我在这里真正苦苦挣扎的是上面使用最小堆的第二种方法的复杂性。

假设列表n中的字符串数为，所有字符串中的字符总数为m。天真的解决方案的上限是O(mn)。binary-concat的精确界限为theta(mlog(n))。这是我无法实现的最小堆方法。

我有点猜测它的上限是O(mlog(n) + nlog(n))。第二项，nlog(n)与维护堆有关。有nconcat，每个concat都会更新中的堆log(n)。如果我们只关注级联的开销，而忽略维护最小堆的开销，则最小堆方法的总体复杂度可以降低到O(mlog(n))。然后，min-heap是比bina​​ry-concat更理想的方法，因为前者mlog(n)是上限，而后者是精确界限。

但是我似乎无法证明这一点，甚至无法找到一个很好的直觉来支持这个猜测的上限。上限可以低于O(mlog(n))吗？