当n1是s1的长度,n2是s2的长度时,为什么这个函数的时间复杂度是O(n1*n2)?
我试图建立一个方程式但失败了。
#include <stdio.h>
int f(char* s1, int i1, char* s2, int i2) {
if (s2[i2] == '\0')
return 1;
if (s1[i1] == '\0')
return 0;
if (s1[i1] != s2[i2])
return f(s1, i1 + 1, s2, 0);
return f(s1, i1+1, s2, i2+1);
}
void main() {
printf("%d", f("hello", 0, "he", 0));
}
最佳答案
对于两次尾调用,函数将i1
递增1
,因此时间复杂度为O(n1)。
请注意,此函数未实现 strstr()
的变体,因为它无法找到 f("aab", 0, "ab", 0)
.
关于c - 找出递归函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44931128/