为什么从“ Cracking the Coding Interview”得出该示例的时间复杂度？ O（k c ^ k）？ [英] Why is the time complexity of this example from "Cracking the Coding Interview" O(k c^k)?

问题描述

此问题来自《破解编码面试第六版》，问题V1.11。

This question is from Cracking the Coding Interview 6th Edition, Question V1.11.

下面的代码打印所有长度为k的字符串，其中字符
按排序顺序排列。它通过生成所有长度为
k的字符串，然后检查每个字符串是否已排序来完成此操作。什么是运行时？

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);
    }

}

答案是O（kc ^ k），其中k是字符串的长度，c是
字母中的字符数。花费O（c ^ k）时间到
生成每个字符串。然后，我们需要检查每一个是否经过
排序，这需要O（k）时间。

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）的来源。

Now, I understand where O(k) comes from but I don't see how O(c^k) came about.

推荐答案

上述算法通过使用一组c个字符递归地生成所有长度为k的可能字符串来工作。您可以从c个字母选择中得出的长度为k的可能字符串数等于c ^k 。例如，如果我要从（a和b）中选择两个字母，并且我有长度为三的字符串，那么我可以制作2 ³ = 8个可能的字符串：

The above algorithm works by recursively generating all possible strings of length k using a set of c choices of characters. The number of possible strings of length k you can make from c choices of letters is equal to c^k. For example, if I have two letters to pick from (a and b) and I have strings of length three, there are 2³ = 8 possible strings I can make:

• aaa


• aab


• aba


• abb


• baa


• bab


• bba


• bbb

• aaa
• aab
• aba
• abb
• baa
• bab
• bba
• bbb

要更好地了解其来源，请注意，每次在字符串末尾添加新字母时，选择该字母的含义，因此可能的字符串数为

To better see where this comes from, notice that every time you add a new letter to the end of the string, you have c choices for what that letter can be, so the number of possible strings is

c· c· ...· c（k次）=

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

c ^k

这意味着上述代码（通过生成每个字符串来工作）必须至少完成 Ω（c ^k ），因为这是最小数目

This means that the above code, which works by generating each of these strings, must do at least Ω(c^k) work, since that's the minimum number of strings to check.

那么对于这些​​字符串中的每个字符串要做什么工作？这是棘手的地方。通过不断从可能的字符列表中追加一个新字符，这些字符串一次构成一个字符。在Java中，附加到字符串会构成字符串的完整副本，因此附加第一个字符的成本（大约）为1，第二个字符（大约）为2，然后为3，然后为4，依此类推。这意味着成本建立长度为k的完整字符串的过程将是

So how much work does it do for each of these strings? Here's where things get tricky. These strings are built up one character at a time by constantly appending a new character from the list of possible characters. In Java, appending to a string makes a full copy of the string, so the cost of appending the first character is (roughly) 1, the second is (roughly) 2, then 3, then 4, etc. This means that the cost of building up a full string of length k will be

1 + 2 + 3 + ... + k

1 + 2 + 3 + ... + k

=Θ（k ² ）

= Θ(k²)

像这里的运行时将是O（c ^k k ² ）而不是O（kc ^k ），因为构建所有这些字符串的成本

So it actually seems like the runtime here would be O(c^k k²) rather than O(k c^k), since the cost of building all those strings adds up rather quickly.

但是，这并不是一个严格的界限。例如，形成字符串 aaa 的某些工作也用于形成字符串 aab ，因为两者字符串以 aa 开头并串联另一个字符组成。

However, that's not a tight bound. For example, some of the work done to form the string aaa is also used to form the string aab, since both strings are formed by starting with aa and concatenating another character in.

为了得到更好的分析，我们可以求和在树的每个级别上执行连接的总工作量。树的第零级具有大小为0的单个字符串，因此不进行任何级联。树的第一层具有大小为1的c个字符串，需要c工作来进行串联。树的第二层具有大小为2的c ² 个字符串，需要2c ² 才能形成。三个级别的第三级具有大小为3的c ³ 字符串，需要3c ³ 的形式形成。更一般而言，级别i需要ic ⁱ 工作来形成。这意味着我们要确定

To get a better analysis, we can sum up the total work done performing concatenations at each level in the tree. The zeroth level of the tree has a single string of size 0, so no concatenations are done. The first level of the tree has c strings of size 1, requiring c work to do to the concatenations. The second level of the tree has c² strings of size 2, requiring 2c² work to form. The third level of the three has c³ strings of size 3, requiring 3c³ work to form. More generally, level i requires icⁱ work to form. This means we want to determine

0c ⁰ + 1c ¹ + 2c < sup> 2 + ... + kc ^k 。

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

总和为θ（kc ^k ），k项的指数较低。

This summation works out to Θ(kc^k), with a lower exponent of the k term.

总结：

• c ^k 项来自需要检查的字符串数。


• k项


• 仔细分析表明，生成所有这些字符串的时间不会影响O（kc ^k ）。

• The c^k term comes from the number of strings that needed to be checked.
• The k term comes from from the work done per string.
• A careful analysis shows that the time to generate all these strings does not affect the overall runtime of O(k c^k).

这篇关于为什么从“ Cracking the Coding Interview”得出该示例的时间复杂度？ O（k c ^ k）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！