为什么这个来自“破解编码面试”的例子的时间复杂度是 O(kc^k)？

Question

本题来自破解编码面试第 6 版，第 V1.11 题。

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

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) 时间。

现在，我明白 O(k) 是从哪里来的，但我不明白 O(c^k) 是怎么来的。

Answer 1

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

• 啊啊啊啊
• aab
• 阿坝
• 艾布
• 咩
• 巴布
• 巴巴
• bbb

为了更好地了解这是从哪里来的，请注意，每次在字符串末尾添加一个新字母时，您都有 c 选择该字母可以是什么，因此可能的字符串数量是

c · c · ... · c (k 次) =

ç ^ķ

这意味着通过生成这些字符串中的每一个来工作的上述代码必须至少执行Ω(c ^k ) 工作，因为这是要检查的最少字符串数。

那么它对每个字符串做了多少工作呢？这就是事情变得棘手的地方。这些字符串是通过不断从可能的字符列表中附加一个新字符来一次构建一个字符的。在 Java 中，追加到一个字符串是一个完整的字符串副本，所以追加第一个字符的成本是（大约）1，第二个是（大约）2，然后是 3，然后是 4，等等。这意味着成本建立一个长度为 k 的完整字符串将是

1 + 2 + 3 + ... + k

= Θ(k ² )

所以实际上这里的运行时似乎是 O(c ^k k ² ) 而不是 O(kc ^k )，因为构建所有这些字符串的成本加起来相当快。

然而，这并不是一个严格的界限。例如，为形成字符串所做的一些工作aaa也用于形成字符串aab，因为两个字符串都是通过以aa另一个字符并连接其中的另一个字符。

为了获得更好的分析，我们可以总结在树的每个级别执行串联所完成的总工作量。树的第 0 层有一个大小为 0 的字符串，因此没有进行连接。树的第一层有 c 个大小为 1 的字符串，需要 c 个工作来完成连接。树的第二层有 c ²个大小为 2 的字符串，需要 2c ^{2 个}工作才能形成。三者的第三层有c ³串大小为3，需要3c ³功才能形成。更一般地说，级别 i 需要 ic ⁱ work 才能形成。这意味着我们要确定

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

这个总和计算为 Θ(kc ^k），与第k项的低指数。

总结一下：

• 的C ^ķ一词源于一个必须检查串的数量。
• k 项来自每个字符串所做的工作。
• 仔细分析，时间生成所有这些字符串不影响Ø总体运行时（KC ^ķ）。

Answer 2

递归调用printSortedStrings形成递归树。因为节点总数大约是最低层节点数的常数因子，并且上层不比最低层做更多的工作，所以只有最低层的成本是显着的。

c以2 和k3为例：

查看树的第一层，会产生：

2(或2^1) 字符串、"a"、"b"。

第二级产生：

4(或2^2) 字符串、"aa"、"ab"、"ba"、"bb"。

第三级产生：

8（或）2^3字符串"aaa"、、、、、、、、、、、。"aab"​​​​"aba""abb""baa""bab""bba""bbb"

按顺序生成下一个字符串的成本是线性的。旧字符串中的字符加上新字符将被复制到新字符串中。

这取决于字符串的长度，因此对于第一级成本为 1，第二级成本为 2，第三级成本为 3。乘以每个级别的项目数：

(2^1)*1 + (2^2)*2 + (2^3)*3 = 34

k如果是，这种模式将继续下去4，那么它将是：

(2^1)*1 + (2^2)*2 + (2^3)*3 + (2^4)*4 = 98

像这样的总和的问题是最后一项大于前面所有项的总和。所以只有最后一项是重要的：

(2^1)*1 + (2^2)*2 + (2^3)*3 < (2^4)*4

因为：

(2^1)*1 + (2^2)*2 + (2^3)*3
< (2^1)*3 + (2^2)*3 + (2^3)*3
= (2^1 + 2^2 + 2^3) * 3
= (2^4 - 2) * 3
< (2^4 - 2) * 4
< (2^4) * 4

所以总和小于2*(2^4)*4, 或2*(c^k)*k, 或O(k c^k)。

在递归结束时，有更多的线性时间工作。有些c^k节点的k工作会带来额外的O(k c^k)成本。所以总成本仍然是O(k c^k)。

O(k c^k)另一件事是 for 循环也需要每个字符串的线性时间，但由于与上面类似的原因，这总共需要。