1. 각 진법 모든 경우의 스트링 만들기 알고리즘

1. 코드

2. 결과

3. 해설

 이 알고리즘은 각 진법의 모든 문자열을 출력하는 알고리즘이다. 리커젼 기법을 사용해서 출력한다.

 리커젼 기법의 시간 복잡도를 알아내는 기법으로 마스터 정리가 있다.

 리커젼에 대한 마스터 정리는 2개가 있는데 먼저 분할 정복 마스터 정리와 감산 정복 마스터 정리가 있다.

 분할 정복 마스터 정리의 수식은 보통 F(n) = F(n/k) + C 이고, 

 감산 정복 마스터 정리의 수식은 보통 F(n) = F(n-k) + C 이다.

 위 코드를 마스터 정리에 대입하면 수식은 F(n,m) = m*F(n-1) + C 이므로 계산하면 

 앞의 계수가 2진법일 경우에는 O(n*m^(n-1)) 이다. 즉, 2진법을 구하는 경우에는 O(2^n) 시간이 걸린다.

 (흔히 시간이 2^n일 경우에는 사용할 수 없는 알고리즘이지만 이 경우에는 이것이 최선이다.)

 최종적으로 이 코드의 시간은 O(k^n) 시간이 걸린다.

 왜냐하면 보통 이런 식으로 추출하는 스트링의 길이는 길지 않기 때문이다. 8의 길이로는 2^8이므로 충분히 계산 할 만하다.

하지만 길이가 길어지면 너무나 오랜 시간이 걸리기 때문에 쓰지 못한다.