我一直在研究一个涉及文本对齐的动态规划问题。我相信我已经找到了一个可行的解决方案,但我对这个算法的运行时间感到困惑。
到目前为止,我所做的研究将此问题的动态规划解决方案描述为 O(N^2) ,其中 N 是要对齐的文本长度。对我来说,这种描述感觉不正确:我可以看到必须进行O(N)调用,因为有N个后缀需要检查,但是对于任何给定的前缀,我们永远不会考虑将换行符(或“split_point”)放置在最大行长度 L 之外。因此,对于任何给定的文本,最多只能放置 L 个拆分点(这假设最坏情况:每个单词恰好为一个字符长)。由于这种认识,这个算法更准确地描述为O(LN)吗?
到目前为止,我所做的研究将此问题的动态规划解决方案描述为 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
提前感谢您的帮助, 伊桑