我想知道以下算法的复杂度,更重要的是,导致推导它的步骤。
我怀疑它是O(length(text)^2*length(pattern)),但我很难解决递归方程。
当在递归调用上进行记忆化(即动态规划)时,复杂度会如何改善?
此外,我希望了解分析这类算法的技巧/书籍的指针。
Python代码:
def count_matches(text, pattern):
if len(pattern) == 0: return 1
result = 0
for i in xrange(len(text)):
if (text[i] == pattern[0]):
# repeat the operation with the remaining string a pattern
result += count_matches(text[i+1:], pattern[1:])
return result
在C语言中:
int count_matches(const char text[], int text_size,
const char pattern[], int pattern_size) {
if (pattern_size == 0) return 1;
int result = 0;
for (int i = 0; i < text_size; i++) {
if (text[i] == pattern[0])
/* repeat the operation with the remaining string a pattern */
result += count_matches(text+i, text_size-(i+1),
pattern+i, pattern_size-(i+1));
}
return result;
}
注意:该算法有意地为每个子字符串重复匹配。请不要关注算法执行何种类型的匹配,而是关注它的复杂度。
抱歉算法中出现的拼写错误已经被修复。
if (text_len < pattern_len) return 0;
。 - jooptext+i, text_size-(i+1), pattern+i, pattern_size-(i+1)
是否应该改为text+i+1, text_size-(i+1), pattern+1, pattern_size-1
?第一个、第三个和第四个参数似乎不正确 O_O ... - Gassa