Understanding Big O notation - Cracking the Coding

问题:

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

The problem goes like this:

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);
}

Book answer:

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?

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. :)

回答1:

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.

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).

Edit: 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.

回答2:

In general the printing of a constant length string is considered constant as well, but if we want to be precise let's consider the print of a single character as the basic operation: this means that to print a k length string we have O(k).

Since we have O(c^k) possible strings and for each of them we have to check if it is sorted (with O(k)) and to print them (another O(k)), the total complexity became O(c^k(k + k)) = O(2c^kk).

But multiplying a function for a constant factor doesn't change it's complexity, and therefore the answer remains O(c^kk).

回答3:

Printing the string is only an extra addition to the k time.

Checking whether each string is sorted is O(k) and say that printing it is O(dk) for some integer d (a constant). Adding the two we get O(k + dk), which can be re written as O(k(1 + d)). Because this just a scalar we know O(k + dk) = O(k) so the answer does not change.