1

以下代码必须根据给定的字典从字符串（没有空格）中识别单独的单词。它尝试在每个字符之后放置一个空格，并检查到目前为止该单词是否在字典中，然后尝试形成一个新单词。如果新词不成功，它会尝试扩展前一个词。你如何计算这样一个程序的内存复杂度？它是指数/阶乘吗？记忆化对复杂性有什么影响吗？（假设如果单词在字典中以恒定时间出现，则 is_word() 返回）

def word_break(string, dictionary, cache, i = 0):
    if i == len(string):
        return []
    else:
        for j in xrange(i+1, len(string)+1):
            chunk = string[i:j]
            if (i, len(chunk)) in cache:
                return cache[(i, len(chunk)]
            if is_word(chunk, dictionary):
                done = word_break(string, dictionary, cache, j)
                if done == False:
                    cache[(i, len(chunk))] = False
                    continue
                else:
                    done.insert(0, chunk)
                    return done
        return False
4

1 回答 1

0

一个小提示：您永远不会将有效单词放入缓存中；你只说False一句话。这是故意的吗？

另外，我相信如果您使用字符串“bun”执行初始调用函数，此代码会将字符串“n”错误地识别为单词。虽然可能是错的。

您使用的内存量主要取决于字典的大小和缓存的大小。字符串的长度至少和缓存一样大（我相信），所以你只需要担心缓存。

缓存的大小取决于单词的确切结构，因为您在缓存中存储的内容取决于单词字符串的结构。

但是，我认为您可以说缓存以字符串的长度为二次边界（ O(n^2) ）。如果您想象一个字符串，其中句子的每个子字符串都不是有效单词，那么它最终会将句子的每个子字符串添加到缓存中，并且长度为 n 的句子中有 n^2 个子字符串。

希望有帮助。

于 2014-02-11T03:45:02.507 回答