java - 为什么这个例子的时间复杂度是从 "Cracking the Coding Interview"O(k c^k)？

Question

此问题来自 Cracking the Coding Interview 第 6 版，问题 V1.11。

The following code prints all strings of length k where the characters are in sorted order. It does this by generating all strings of length k and then checking if each is sorted. What is the runtime?

package QVI_11_Print_Sorted_Strings;


public class Question {

    public static int numChars = 26;

    public static void printSortedStrings(int remaining) {
        printSortedStrings(remaining, "");
    }

    public static void printSortedStrings(int remaining, String prefix) {
        if (remaining == 0) {
            if (isInOrder(prefix)) {
                System.out.println(prefix);
            }
        } else {
            for (int i = 0; i < numChars; i++) {
                char c = ithLetter(i);
                printSortedStrings(remaining - 1, prefix + c);
            }
        }
    }

    public static boolean isInOrder(String s) {
        for (int i = 1; i < s.length(); i++) {
            int prev = ithLetter(s.charAt(i - 1));
            int curr = ithLetter(s.charAt(i));
            if (prev > curr) {
                return false;
            }
        }
        return true;
    }

    public static char ithLetter(int i) {
        return (char) (((int) 'a') + i);
    }

    public static void main(String[] args) {
        printSortedStrings(5);
    }

}

The answer is O(k c^k) where k is the length of the string and c is the number of characters in the alphabet. It takes O(c^k) time to generate each string. Then, we need to check that each of these is sorted, which takes O(k) time.

现在，我了解 O(k) 的来源，但我不明白 O(c^k) 是如何产生的。

Answer 1

上述算法的工作原理是使用一组 c 个字符选择递归地生成所有可能的长度为 k 的字符串。从 c 个字母中可以组成的长度为 k 的可能字符串的数量等于 c^k。例如，如果我有两个字母可供选择(a 和 b)并且我有长度为 3 的字符串，那么我可以制作 2³ = 8 个可能的字符串:

• 啊啊
• aab
• 阿巴
• ab
• 咩
• 宝贝
• bba
• bb

为了更好地了解这是从哪里来的，请注意每次在字符串末尾添加一个新字母时，您都有 c 个选项可以选择该字母，因此可能的字符串数是

c · c · ... · c (k times) =

c^k

这意味着上面的代码通过生成这些字符串中的每一个来工作，必须至少 Ω(c^k) 工作，因为这是最小数量要检查的字符串。

那么它对每个字符串做了多少工作呢？这就是事情变得棘手的地方。这些字符串是通过不断地从可能字符列表中附加一个新字符而一次构建一个字符的。在 Java 中，附加到字符串会生成字符串的完整副本，因此附加第一个字符的成本(大约)为 1，第二个字符(大约)为 2，然后是 3，然后是 4，等等。这意味着成本构建一个长度为 k 的完整字符串将是

1 + 2 + 3 + ... + k

= Θ(k²)

所以这里的运行时间实际上看起来是 O(c^k k²) 而不是 O(k c^k)，因为构建所有这些字符串的成本加起来相当快。

然而，这并不是一个严格的界限。例如，为形成字符串 aaa 所做的一些工作也用于形成字符串 aab , 因为两个字符串都是从 aa 开始形成的并连接另一个字符。

为了获得更好的分析，我们可以总结在树的每个级别上执行串联所完成的总工作量。树的第 0 层有一个大小为 0 的字符串，因此没有进行任何连接。树的第一层有 c 个大小为 1 的字符串，需要进行 c 次连接操作。树的第二层有 c² 个大小为 2 的字符串，需要 2c² 的工作才能形成。三层中的第三层有 c³ 个大小为 3 的字符串，需要 3c³ 才能形成。更一般地说，级别 i 需要 icⁱ 工作才能形成。这意味着我们要确定

0c⁰ + 1c¹ + 2c² + ... + kc^k.

此求和结果为 Θ(kc^k)，其中 k 项的指数较低。

总结:

• c^k 项来自需要检查的字符串数。
• 第 k 项来自每个字符串完成的工作。
• 仔分割析表明，生成所有这些字符串的时间不会影响 O(k c^k) 的整体运行时间。