这个检查排列的递归函数的时间复杂度是多少？

Question

以下函数的时间复杂度是多少？它如何随着长度/字符串检查而变化？我注意到长度为 6 时，函数执行速度很快。一旦我将字符串增加到“abcdefg”并将长度增加到 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;
    }

Answer 1

看起来效率O(26^length)，所以，可怕。

函数中的各种顶层if语句都是常量时间，所以我们不用管它们，但是for循环每次调用会执行26次，并且每次它都会再次调用自己，深度为 length。因此，总运行时间约为 26 的 length 次方。作为复杂度class，这可以减少到O(x^n)，或'exponential'。

你没有在你的问题中提到这个函数应该实现什么（它看起来是一种非常低效的方法"abcdef".startsWith(str)），所以我不能真正帮助优化。

这个检查排列的递归函数的时间复杂度是多少？

What is the time complexity of this recursive function that checks for a permutation?

java

algorithm

recursion

big-o