java—检查置换的递归函数的时间复杂度是多少?

kxeu7u2r  于 2021-07-07  发布在  Java
关注(0)|答案(1)|浏览(416)

以下函数的时间复杂度是多少?在检查字符串时,它是如何与长度/相关的变化的?我注意到长度为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;
    }
des4xlb0

des4xlb01#

看起来效率很高 O(26^length) ,太可怕了。
各种顶级 if 函数中的语句是常量时间,因此我们不必担心它们,但是 for 循环将在每次调用中执行26次,每次都会再次调用自己,深度为 length . 因此,总运行时间的顺序是 26 以…的力量 length . 作为一个复杂性类,这可以简化为 O(x^n) ,或“指数”。
在你的问题中你没有提到这个函数应该实现什么(它看起来是一个非常低效的方法) "def".startsWith(str) ),所以我真的不能帮助优化。

相关问题