以下函数的时间复杂度是多少?在检查字符串时,它是如何与长度/相关的变化的?我注意到长度为6时,函数执行速度很快。一旦我将字符串增加到“defg”,长度增加到7,它就会开始减速。对于您添加的每个附加字符,关系是否为指数关系?
public static boolean permutate(String str, int length)
{
if (length < 0)
return false;
if (str.equals("abcdef"))
return true;
for(char c = 'a'; c <= 'z'; c++)
{
if(permutate(str + c, length - 1))
return true;
}
return false;
}
1条答案
按热度按时间des4xlb01#
看起来效率很高
O(26^length)
,太可怕了。各种顶级
if
函数中的语句是常量时间,因此我们不必担心它们,但是for
循环将在每次调用中执行26次,每次都会再次调用自己,深度为length
. 因此,总运行时间的顺序是26
以…的力量length
. 作为一个复杂性类,这可以简化为O(x^n)
,或“指数”。在你的问题中你没有提到这个函数应该实现什么(它看起来是一个非常低效的方法)
"def".startsWith(str)
),所以我真的不能帮助优化。