java - 计算我的程序的 Big O 复杂度

Question

我的程序打印具有双字母的单词的所有排列 例如 在“Helloo”这个词中

结果将是: [嘿嘿，嘿嘿，你好，你好]

private List<String> doubleLetterPermute(String start, String ending, List<String> possibleWords) {
    String prev = "";
    for (int i = 0; i < ending.length(); i++) {
        String letter = String.valueOf(ending.charAt(i));
        // its a double letter
        if (letter.equals(prev)) {
            doubleLetterPermute(start + ending.substring(0, i), ending.substring(i + 1), possibleWords);
            doubleLetterPermute(start + ending.substring(0, i + 1), ending.substring(i + 1), possibleWords);
        }
        prev = letter;
    }
    possibleWords.add(start + ending);
    return possibleWords;
}

我不知道当递归函数出现时如何计算复杂度。 它循环 n 次，其中 n 是单词中的字符数，O(n)，但我在每次出现双字母时拆分单词，那么它如何以大 O 表示法显示？

Answer 1

为了计算复杂性，您需要考虑最坏和最好的情况。

最多，你会得到一个长度为 N 且没有双字母的单词，比方说“abcde”。您的复杂性将为 O(n)，因为您只有一个大小为 N 的循环。

在最坏的情况下，您会得到一个长度为 N 且具有相同字母的单词，例如“aaaaa”。在本例中，您有一个大小为 N 的循环，其中包含 2 个大小为 (N - i) 的循环。因此，复杂度为 O(2(n-i)*n) 或 O(n^2)。