N M2(by Choice)

알고리즘 생각

1,2,3,...N 사이의 자연수 n에 대해 선택O, 선택X 의 관점에서 생각해보면 각각의 수는 2가지의 경우의 수를 갖는다. N개의 수 * 2가지 = 총 2^N 경우의 수가 나온다.

한가지 경우는 배열에 수를 저장하는 것이므로 O(1)이라고 하면 총 2^N 개의 경우이므로 시간복잡도는 O(2^N)이라고 할 수 있다.

앞서 살펴본 풀이법은 각 자리수별로 N가지, N-1가지, N-2가지,..이므로 N!이다. (중복X, 오름차순 수열인 경우 N가지, N-i가지(i는 앞의수),...이지만 시간복잡도는 대략적인 것을 구하기 때문에 결국 N*(N-1)*(N-2)*...라고 할 수 있고 이것은 N!이다.)

N!>>>2^N 이므로 선택관점(2^N)이 더 좋다고 할 수 있다!

재귀 함수 실행 흐름