理解大O符号 - 破解编码面试

Question

我需要帮助理解作者如何在Big O章节中得到问题11的答案.

问题是这样的:

以下代码打印长度为k的所有字符串,其中字符按排序顺序排列.它通过生成长度为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 ² c ^k)吗？

此外,任何关于能够快速告知在此代码的运行时间中存在指数部分的建议将非常感激.:)

Answer 1

简而言之,没有.正确的答案是书中的O(kc ^k).

在你查完字符串以检查它的字符是否被排序后,这将花费O(k),打印它只会添加O(k) - 这不会改变你的复杂性.

假设测试字符串是否被排序需要a*k操作,并且打印它需要b*k.然后每个字符串的操作总数最多为(a+b)*kO(k).

编辑:关于问题的第二部分,遍历所有具有固定长度的单词将导致指数运行时复杂性,因为有c ^k这样的单词,其中c是字母表的大小,并且k是单词的长度.