교안 속의 조합의 시간복잡도에 대한 질문

RokiePlayer

작성한 질문수 10

0

안녕하세요. RokiePlayer님 ㅎㅎ 

코테 잘보셨나요? 여기서 추천한 문제유형이 나와서 저도 정말 기분이 좋네요.ㅎㅎ

 

nH3 정도의 문제여서 바로 저번 문제에서 본 대로 3중 루프문을 사용했습니다.

 >> 3중루프문을 써서 중복조합말고 조합을 하시는 것을 추천드립니다. 

for i = 0 ~ n

  for j = 0 ~ n 

이런식으로 푸신 것 같은데

for i = 0 ~ n 

  for j = i + 1 ~ n

이런식으로 푸시면 "중복조합" 아닌 "조합"이 되는 것이죠.

 

근데 돌아오고 보니 그냥 교안에 있던 조합 재귀 함수를 만들어서도 풀 수 있었습니다.

그래서 여기서 질문인 게 같은 조건이면 어느 쪽이 시간복잡도 측면에서 유리한 건가요?

결국 해야 할 연산의 양이 똑같을 거 같습니다. 

 >> 연산의 양은 똑같습니다. 재귀함수도, 반복문을 통해서 하든 똑같은 "조합"이라면요. 하지만 시간은 반복문이 훨씬 빠릅니다. 물론 문제마다 다른 부분이 있겠지만 보통은 반복문이 빠릅니다. 왜냐면 재귀함수를 만든다고 했을 때 "함수를 반복해서 만드는 비용"이 발생하기 때문이죠.

 

또 질문사항있으시면 언제든 말씀 부탁드립니다. 

감사합니다. 

강사 큰돌 올림.