动态规划文本对齐的时间复杂度

Question

我一直在研究 dynamic programming problem involving the justification of text。我相信我已经找到了一个可行的解决方案，但我对该算法的运行时间感到困惑。

到目前为止，我所做的研究将此问题的动态规划解决方案描述为 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

在此先感谢您的帮助，伊森

Answer 1

首先，您的实施与您想要的理论效率相去甚远。您在调用中记忆了一个长度为 N 的字符串，这意味着查找数据的缓存副本可能是 O(N)。现在开始进行多个缓存调用，您已经超出了复杂性预算。

这可以通过将文本移到函数调用之外并只传递起始位置的索引和长度 L 来解决。您还在循环内部进行连接，这是一个 O(L) 操作。小心点，您可以改为 O(1) 操作。

完成后，您将进行 O(N*L) 操作。正是出于您所想的原因。

动态规划文本对齐的时间复杂度

Time Complexity of Text Justification with Dynamic Programming

algorithm

big-o

dynamic-programming

time-complexity