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

Question

我需要帮助来理解作者是如何得到 Big O 章节中问题 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 its runtime?

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), 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²c^k)?

此外，我们将不胜感激任何有关能够快速判断此代码的运行时中存在指数部分的建议。 :)

Answer 1

简而言之，没有。正确答案是书上的O(kc^k)。

在你检查一个字符串以检查它的字符是否有序后，这将花费 O(k)，打印它只会添加 O(k) - 这不会改变你的复杂性。

假设测试一个字符串是否有序需要 a*k 次操作，打印它需要 b*k 次。那么每个字符串的操作总数最多为 (a+b)*k 仍然是 O(k).

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

Answer 2

打印字符串只是 k 时间的额外增加。

检查每个字符串是否已排序是 O(k) 并说打印它是 O(dk) 对于某个整数 d（常量）。将两者相加得到 O(k + dk)，可以改写为 O(k(1 + d))。因为这只是我们知道的标量 O(k + dk) = O(k) 所以答案不会改变。

Answer 3

一般来说，打印一个常量长度的字符串也被认为是常量，但是如果我们想要更精确的话，让我们将打印单个字符作为基本操作：这意味着要打印一个 k 长度的字符串，我们有O(k)。

因为我们有 O(c^k) 个可能的字符串，对于每个字符串，我们必须检查它是否已排序（使用 O(k)）并打印它们（另一个 O(k))，总复杂度变为 O(c^k(k + k)) = O(2c^kk)。

但是将一个函数乘以一个常数因子并不会改变它的复杂性，因此答案仍然是 O(c^kk).

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

Understanding Big O notation - Cracking the Coding Interview

java

sorting

algorithm

big-o