0

我的程序打印包含双字母的单词的所有排列例如在单词'Helloo'中

结果将是：[heloo, helo, hello, hello]

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 符号中是如何显示的？

4

1 回答 1

1

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

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

在最坏的情况下，你会有一个长度为 N 的单词和同一个字母，比如说“ aaaa ”。在这种情况下，您有一个大小为 N 的循环，其中包含 2 个大小为 (N - i) 的循环。因此，复杂度将是 O(2(ni)*n) 或 O(n^2)。

于 2013-04-22T19:29:42.347 回答