最小化连接成本的解决方案的复杂性分析
Complexity analysis of a solution to minimizing concat cost
这是关于分析一个热门面试问题的解决方案的复杂性。
问题
有一个函数 concat(str1, str2) 可以连接两个字符串。该函数的成本是通过两个输入字符串的长度 len(str1) + len(str2) 来衡量的。实现 concat_all(strs) 仅使用 concat(str1, str2) 函数连接字符串列表。目标是最小化总连接成本。
警告
通常在实践中，您会非常谨慎地连接循环中的字符串对。可以找到一些很好的解释 here and 。在现实中，我亲眼目睹了一次由此类代码引起的严重程度为 1 的事故。除了警告，假设这是一个面试问题。我真正感兴趣的是围绕各种解决方案的复杂性分析。
如果你想思考这个问题，你可以在这里暂停。我将在下面揭示一些解决方案。
解决方案
- 天真的解决方案。遍历列表并连接
def concat_all(strs):
result = ''
for str in strs:
result = concat(result, str)
return result
- 最小堆解决方案。这个想法是首先连接较短的字符串。根据字符串的长度维护字符串的最小堆。每个连接都连接最小堆中的 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()
- 二进制连接。可能直观上不是很清楚。但另一个好的解决方案是递归地将列表分成两半并连接起来。
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) 与维护堆相关；有 n 个连接，每个连接都会更新 log(n) 中的堆。如果我们只关注连接的成本而忽略维护最小堆的成本，则最小堆方法的整体复杂度可以降低到O(mlog(n))。那么最小堆是比二进制连接更优化的方法，因为前者 mlog(n) 是上限，而后者是确切的界限。
但我似乎无法证明这一点，甚至无法找到很好的直觉来支持猜测的上限。上限可以低于O(mlog(n))吗？
让我们称 字符串 1 到 n 的长度，m 是所有这些值的总和。
对于天真的解决方案，如果
m1
几乎等于 m，正如您指出的那样，您获得了 O(nm) 复杂度。
对于最小堆，最坏情况有点不同，它在于任何字符串具有相同的长度。在那种情况下，它将完全按照二进制连接的情况 3. 工作，但您还必须维护最小堆结构。所以是的，它会比现实生活中的案例 3 更昂贵。然而，从复杂性的角度来看，两者都将在 O(m log n) 中，因为我们有 m > n 并且 O(m log n + n log n) 可以减少为 O(m log n)。
为了更严格地证明最小堆复杂度，我们可以证明，当我们取一组k个字符串中最小的两个字符串，并用S表示这两个最小字符串的和，则我们有：(m-S)/(k-1) >= S/2（这只是意味着两个最小字符串的平均值小于 k-2 其他字符串的平均值）。重新制定导致 S <= 2m/(k+1)。让我们把它应用到最小堆算法中：
- 第一步，我们可以证明我们取的2个字符串的总长度最多为2m/(n+1)
- 第一步，我们可以证明我们取的2个字符串的总长度最多为2m/(n)
- ...
- 在最后一步，我们可以证明我们所取的2个字符串的总长度最多为2m/(1)
因此min-heap的计算时间是2m*[1/(n+1) + 1/n + ... + 1/2 + 1]，在O(m log n)
这是关于分析一个热门面试问题的解决方案的复杂性。
问题
有一个函数 concat(str1, str2) 可以连接两个字符串。该函数的成本是通过两个输入字符串的长度 len(str1) + len(str2) 来衡量的。实现 concat_all(strs) 仅使用 concat(str1, str2) 函数连接字符串列表。目标是最小化总连接成本。
警告
通常在实践中，您会非常谨慎地连接循环中的字符串对。可以找到一些很好的解释 here and
如果你想思考这个问题，你可以在这里暂停。我将在下面揭示一些解决方案。
解决方案
- 天真的解决方案。遍历列表并连接
def concat_all(strs): result = '' for str in strs: result = concat(result, str) return result - 最小堆解决方案。这个想法是首先连接较短的字符串。根据字符串的长度维护字符串的最小堆。每个连接都连接最小堆中的 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() - 二进制连接。可能直观上不是很清楚。但另一个好的解决方案是递归地将列表分成两半并连接起来。
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) 与维护堆相关；有 n 个连接，每个连接都会更新 log(n) 中的堆。如果我们只关注连接的成本而忽略维护最小堆的成本，则最小堆方法的整体复杂度可以降低到O(mlog(n))。那么最小堆是比二进制连接更优化的方法，因为前者 mlog(n) 是上限，而后者是确切的界限。
但我似乎无法证明这一点，甚至无法找到很好的直觉来支持猜测的上限。上限可以低于O(mlog(n))吗？
让我们称
对于天真的解决方案，如果
m1几乎等于 m，正如您指出的那样，您获得了O(nm)复杂度。对于最小堆，最坏情况有点不同，它在于任何字符串具有相同的长度。在那种情况下，它将完全按照二进制连接的情况 3. 工作，但您还必须维护最小堆结构。所以是的，它会比现实生活中的案例 3 更昂贵。然而，从复杂性的角度来看，两者都将在
O(m log n)中，因为我们有m > n并且O(m log n + n log n)可以减少为O(m log n)。
为了更严格地证明最小堆复杂度，我们可以证明，当我们取一组k个字符串中最小的两个字符串，并用S表示这两个最小字符串的和，则我们有：(m-S)/(k-1) >= S/2（这只是意味着两个最小字符串的平均值小于 k-2 其他字符串的平均值）。重新制定导致 S <= 2m/(k+1)。让我们把它应用到最小堆算法中：
- 第一步，我们可以证明我们取的2个字符串的总长度最多为2m/(n+1)
- 第一步，我们可以证明我们取的2个字符串的总长度最多为2m/(n)
- ...
- 在最后一步，我们可以证明我们所取的2个字符串的总长度最多为2m/(1)
因此min-heap的计算时间是2m*[1/(n+1) + 1/n + ... + 1/2 + 1]，在O(m log n)