使用动态规划进行文本对齐的时间复杂度

Question

我一直在研究一个涉及文本对齐的动态规划问题。我相信我已经找到了一个可行的解决方案，但我对这个算法的运行时间感到困惑。

到目前为止，我所做的研究将此问题的动态规划解决方案描述为 O(N^2) ，其中 N 是要对齐的文本长度。对我来说，这种描述感觉不正确：我可以看到必须进行O（N）调用，因为有N个后缀需要检查，但是对于任何给定的前缀，我们永远不会考虑将换行符（或“split_point”）放置在最大行长度 L 之外。因此，对于任何给定的文本，最多只能放置 L 个拆分点（这假设最坏情况：每个单词恰好为一个字符长）。由于这种认识，这个算法更准确地描述为O（LN）吗？

@memoize
def justify(text, line_length):

    # If the text is less than the line length, do not split
    if len(' '.join(text)) < line_length:
        return [], math.pow(line_length - len(' '.join(text)), 3)

    best_cost, best_splits = sys.maxsize, []

    # Iterate over text and consider putting split between each word
    for split_point in range(1, len(text)):
        length = len(' '.join(text[:split_point]))

        # This split exceeded maximum line length: all future split points unacceptable
        if length > line_length:
            break

        # Recursively compute the best split points of text after this point
        future_splits, future_cost = justify(text[split_point:], line_length)
        cost = math.pow(line_length - length, 3) + future_cost

        if cost < best_cost:
            best_cost = cost
            best_splits = [split_point] + [split_point + n for n in future_splits]

    return best_splits, best_cost

提前感谢您的帮助， 伊桑

- Ethan Welsh

---

这里的规范DP算法检查所有起始和结束位置的惩罚（或成本）。即) cost[i][j] = penaltyForWordsOnLineBetween(i,j)对于所有有效的位置i，j这是N ^ 2 - Chris

Answer 1

首先，你的实现与你期望的理论效率相差甚远。在调用中，你正在将长度为N的字符串进行记忆化处理，这意味着查找缓存数据的复杂度可能是O(N)。现在开始进行多个缓存调用，你已经超出了复杂度预算。

通过将文本移到函数调用外部并仅传递起始位置的索引和长度L，可以解决这个问题。你还在循环内部执行了一次join操作，其复杂度为O(L)。通过一些小心的处理，你可以将其变成一个O(1)操作。

完成以上步骤后，你将执行O(N*L)次操作，正如你所想的那样。

- btilly

---

备忘录优化是个好主意。 - Chris