백 트래킹의 기본이 재귀 함수를 호출하는 것이잖아요.

함수 호출 비용이 일단 엄청나게 들어갑니다.

복귀 포인터 저장하고요. (어딘가에 저장하겠죠?)

베이스 포인터도 바꿀 거고, 인자를 넘겨받으면서 스택 포인터도 증가시킬 거고..

1번 premutation이 돌 때마다 10번을 수행하겠네요?

10! x 10 = 3628만번. 여기에 연산 몇 번 하면 시간 초과가 나는 건 당연하겠죠..

단순히 시간을 줄이는 쉬운 방법은.

(1) 어짜피 문자열의 최대 길이가 10입니다.

(2) 10개 모두 다 다르다면 백트랙킹을 할 필요가 있을까요?

(3) 10개 중에서 일부만 같은 경우는 어짜피 걸러지기 때문에, 실제 수행 횟수는 얼마 되지 않습니다.

다만, 재귀 호출에 의한 것이 문제이지요. 계속 함수를 불렀다가. 스택 쌓았다가 팝 했다가.

최악의 경우에는, 2개만 같고, 나머지가 모두 다른 경우

그러니까 aabcdefghi 같은 경우인데, 이 경우, 함수 호출 횟수가 811만번이나 되네요.

물론 prem 자체는 그리 많지는 않아 보입니다만..

하지만, back - tracking을 하면서 부르는 함수 호출은 쉽게 개선되지 않죠.

https://www.nayuki.io/page/nex...

이 자료를 참고하시면 next_permutation을 구현하실 수는 있으실 겁니다.

물론 c++ 알고리즘에도 있고요.

그리고, 같은 문자 2개, 나머지는 모두 다른 것인 경우

set에 142만개 가량이 들어갑니다. set이라던지, map은 보통 레드 블랙 트리로 구현되는데요.

이 친구는 이진 트리의 단점 (한 쪽으로 치우치는 현상)을 해결하기 위해서 나온 것이죠.

거의 (?) 라고는 하기 그렇지만. 그래도 한쪽으로 치우치지 않고 균형있게 배치가 되므로

탐색이나 추가 같은 복잡도가 logn이 되고요.

https://en.wikipedia.org/wiki/...

이걸 n개에 대해서 수행하면 nlogn쯤 되겠죠? 여기서 142만 x 20 = 2820만.

그런데, 문제는 공간 복잡도입니다. 문자열의 길이가 10이므로

최대 142만 x 10 = 1420만이 되겠네요. 헤헤~

이렇게 데이터가 커지면. 곤란해 질 수 있는게.

트리 같은 경우는 연속적이라고 하기 그래요. (배열은 연속적이지만)

지역성의 원리랑도 조금은 연관이 되는 이야기일 수 있는데요.

간단하게 행렬 A와 B 곱셈을 한 번은 그냥 깡으로 해 보시고, 다른 한 번은 A를 transpose 하고 B와 곱해보세요.

데이터 사이즈가 굉장히 큰 경우는 몇 배까지 차이가 납니다. 한 5배? 7배?

결론은, perm 알고리즘에 대해서 알아보시는 게 좋을 듯 싶네요.