了解大符号-破解编码面试

Question

我需要帮助，以帮助作者了解“大O”一章中问题11的答案。

问题是这样的：

下面的代码打印所有长度为k的字符串，其中字符按html" target="_blank">排序顺序排列。它通过生成所有长度为k的字符串，然后检查每个字符串是否已排序来做到这一点。它的运行时间是多少？

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); // Printing the string
        }
    } 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(2);
}

预订答案：

O（kc k），其中k是字符串的长度，c是字母中的字符数。生成每个字符串需要O（c k）时间。然后，我们需要检查所有这些是否已排序，这需要O（k）时间。

请注意，上面的答案未考虑打印字符串，但是在其他问题中我却发现了相反的情况。

您何时考虑在运行时中打印字符串？

这是正确的答案 O（k 2 c k）吗？

此外，任何能够快速告诉您此代码运行时中存在指数部分的建议都将不胜感激。:)

Answer 1

简而言之，没有。正确答案是书中的O（kc k）。

在检查完一个字符串以检查其字符是否有序（占用O（k））之后，打印该字符串将仅增加O（k）-这不会改变您的复杂性。

假设测试字符串是否已排序需要进行a*k操作，而打印则需要进行操作b*k。这样，每个字符串的操作总数最多为(a+b)*kO（k）。

编辑： 关于问题的第二部分，遍历具有固定长度的所有单词将导致指数级的运行时复杂度，因为存在c
k个这样的单词，其中c的大小是字母的大小，也是k该单词的长度。