Понимание нотации Big O - взломание кода

Мне нужна помощь, чтобы понять, как автор получил ответ на проблему 11 в главе Big O.

Проблема следующая:

Следующий код печатает все строки длины 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)?

Кроме того, следует приветствовать любые советы о том, чтобы быстро сказать, что экспоненциальная часть во время выполнения этого кода будет оценена.:)

Ответы

Ответ 1

Короче говоря, нет. Правильный ответ: O (kc ^k), как в книге.

После того, как вы перешли строку, чтобы проверить, были ли ее символы заказаны, что будет делать O (k), печать будет добавлять только O (k) - это не изменит вашу сложность.

Предположим, что проверка того, упорядочена ли строка, принимает операции a*k, а для печати требуется b*k. Тогда общее количество операций для каждой строки не превышает (a+b)*k, которое все еще равно O (k).

Изменить: Что касается второй части вашего вопроса, перебор всех слов с определенной фиксированной длиной приведет к экспоненциальной сложности выполнения, так как есть c ^k такие слова где c - размер алфавита, а k - длина слова.

Ответ 2

В общем случае печать строки с постоянной длиной также считается постоянной, но если мы хотим быть точным, рассмотрим печать одного символа в качестве основной операции: это означает, что для печати строки длины ak имеем O(k).

Так как мы имеем O (c ^k) возможные строки, и для каждого из них мы должны проверить, сортируется ли она (с O (k)) и печатать их (другое O (k)), полная сложность стала O (c ^k (k + k)) = O (2c ^k k).

Но умножение функции на постоянный множитель не меняет ее сложности, и поэтому ответ остается O (c ^k k).

Ответ 3

Печать строки - это дополнительное дополнение к времени k.

Проверка сортировки каждой строки - O(k) и говорит, что ее печать O(dk) для некоторого целого d (константа). Добавив два, получим O(k + dk), который можно записать в виде O(k(1 + d)). Поскольку это просто скаляр, мы знаем O(k + dk) = O(k), поэтому ответ не меняется.