理解大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) 是否为正确答案？

另外，如何快速判断这段代码运行时间中是否存在指数部分？:)

- Esdras Lopez

---

你是如何得出 O(k²c^k) 的？其中的“2”从哪里来的（教科书上只有 O(k c^k)）？ - Thilo

如果你想考虑将字符串打印出来，那么对于每个找到的答案来说它是O（k）。因此，你可以将其视为“检查”的一部分（每个候选人已经是O（k）），而不会增加复杂性。 - Thilo

为什么字符串连接 prefix + c 不会影响复杂度？我的理解是它本身具有 O(n) 的复杂度。我错过了什么吗？ - chalimartines

字符串连接的复杂性在最终的 k 系数中有所体现。我以为它会更糟糕，因为它是在每次调用时完成的，而不仅仅是在最后，但总调用次数与最后的调用次数成比例，所以并没有影响。 - fgb

Answer 1

简而言之，不行。正确答案是书中提到的O(kc^k)。

当您检查一个字符串的字符是否有序时，需要O(k)的时间，打印它只需要增加O(k)的时间 - 这不会改变您的复杂度。
假设测试一个字符串是否有序需要a*k个操作，打印需要b*k个操作。那么每个字符串的总操作次数最多为(a+b)*k, 仍然是O(k)。
编辑：关于您问题的第二部分，遍历所有长度固定的单词将导致指数级运行时间复杂度，因为有c^k这样的单词数量，其中c是字母表的大小，k是单词的长度。

- johnnyaug

---

我现在明白了。字符串打印发生的时间（最多）是在isInOrder执行后每次发生，这就是为什么它不是O(k*k)，而是O(k + k)。O(k + k)变成了O(2k)，但我们去掉了常数。我的逻辑正确吗？我的想法有道理吗？ - Esdras Lopez

太好了！感谢您的帮助并回答我问题的第二部分。 - Esdras Lopez

Answer 2

通常情况下，打印一个固定长度的字符串也被认为是常量级操作，但如果我们想要更加精确，让我们将单个字符的打印视为基本操作：这意味着打印一个长度为k的字符串需要O(k)的时间。

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

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

- SimoV8

Answer 3

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

检查每个字符串是否排序需要 O(k) 的时间，并且打印它需要d（常数）次 O(k) 的时间，即总共需要 O(dk) 的时间。将这两个时间相加得到 O(k + dk)，可以重写为 O(k(1 + d))。因为这只是一个标量，我们知道 O(k + dk) = O(k)，所以答案不会改变。

- flakes