了解大符号-破解编码面试 [英] Understanding Big O notation - Cracking the Coding Interview

问题描述

我需要帮助来了解作者如何获得大O一章中问题11的答案。

I need help understanding how the author got the answer of problem 11 in the Big O chapter.

问题是这样的：

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

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 ），其中k是字符串的长度，c是字母中的字符数。生成每个字符串需要O（c ^k ）时间。然后，我们需要检查每个字符串是否已排序，这需要O（k）时间。

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.

注意打印字符串是上面的答案中没有考虑到这一点，但是在其他问题上我却看到了相反的情况。

Notice that printing the string is not taken into account in the answer above, but I've seen the opposite in other problems.

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

When do you take into account printing the string in the runtime?

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

Would this be the correct answer O(k²c^k)?

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

Also, any advice on being able to quickly tell that there's an exponential part in the runtime of this code would be greatly appreciated. :)

推荐答案

总之，没有。正确答案是书中的O（kc ^k ）。


在检查完字符串以检查其字符是否有序之后，这将花费O（k），将其打印只会增加O（k），这不会改变您的复杂性。

In short, no. The correct answer is O(kc^k) as in the book.

After you went over a string to check if its characters were ordered, which would take O(k), printing it would add only O(k) - which does not change your complexity.

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

Suppose testing whether a string is ordered takes a*k operations, and printing it takes b*k. Then the total number of operations for each string is at most (a+b)*k which is still O(k).

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

Regarding the second part of your question, going over all words with some fixed length will result in an exponential runtime complexity, since there are c^k such words where c is the size of the alphabet and k is the length of the word.

这篇关于了解大符号-破解编码面试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！