책에서 본 Big-O 문제인데 이해가 잘 안되는 부분이 있네요.

void permutation(String str) {
    permutation(str, "");
}

void permutation(String str, String prefix) {
    if (str.length() == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < str.length(); ++i) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

출처: <코딩 인터뷰 완전 분석 6/E>

어떤 문자열로 나타낼 수 있는 순열의 개수를 구하는 코드인데요,

길이가 n인 문자열이 주어졌을 때 나올 수 있는 순열의 개수는 n!이므로, permutation() 함수의 호출 횟수는 호출 트리(Call Tree)의 깊이 n을 고려해서 n*n!이라고 합니다.

그리고 하나의 permutation() 함수 내에서 걸리는 시간은, 문자열 전체를 출력하는데 걸리는 시간 O(n) / 문자열 전체를 rem으로 연결하는데 걸리는 시간 O(n) 이므로 n이라고 설명되어 있습니다.

그래서 총 시간 복잡도는 O(n^2 * n!)이 된다고 하는데…약간 이해가 안 되는 부분이 있어서요.

permutation(String str, String prefix) 함수 내에서 문자열을 연결하는 작업은 for문에 의해 수행됩니다. 문자열 str의 길이가 n이라면 문자열을 연결할 때 소요되는 시간 * for문의 반복 횟수를 계산해서 n^2 이 되어야 하는 것 아닌가요? 어째서 n이 되는지가 궁금합니다.

안녕하세요.

두 문자열을 연결할때 시간복잡도가 O(n^2)이라고 생각하시는건가요?

1 Like

for문의 반복 횟수는 처음에 말씀하신 n * n!에 포함해서 계산되어 있는 것 같습니다.

1 Like

사실 재귀 없이, 그것도 in place로 수행할 방법이 있긴 한데…

https://en.cppreference.com/w/cpp/algorithm/next_permutation

두 문자열을 연결할 때 O(n)이 소모되고, for문을 n번 반복하니 O(n)을 곱해서 O(n^2)이라고 생각하였습니다.

음 그런가요. 이거 좀 헷갈리네요;
책에는 "전체 호출 트리의 노드 개수를 생각해보면, 노드의 최대 개수는 n*n!개를 넘을 수 없다"라고 쓰여 있거든요. 그래서 트리의 모든 레벨이 n!개의 노드를 갖고 있다고 가정한 건가? 이렇게 생각했던 것 같아요. 순열 트리의 깊이는 n이므로…

N인 for문을 n번 반복하는게 트리의 깊이 잖아용

이렇게 또 저의 멍청함이 드러나버렸군요…:joy:
답변 감사합니다.

아니에요 ㅎㅎㅎ

누구나 처음보는 개념에 대해서는 헷갈릴 수밖에요 ㅎㅎㅎ