1주차 개념 #7. 문제로 연습하는 시간복잡도 Q5

1주차 개념 #7. 문제로 연습하는 시간복잡도 Q5

여러분 이 코드의 시간복잡도는 얼마일까요?

힌트는

등비수열의 합이 힌트입니다.

우리가 이런 for 문 같은 경우에는 시간 복잡도가 O(N)이라는 게 되게 쉽잖아요.

그런데 우리가 익숙치 않은거는 사실은 이러한 재귀함수, recursion이 좀 어렵습니다.

근데 여러분 제가 지금부터 정말 쉽게 이 재귀함수의 시간 복잡도를 구하는 것을 알려드리고자 합니다. 기억하세요.

재귀함수의 시간 복잡도는 재귀함수의 main 로직이 있어요. 재귀함수의 시간복잡도는 main 로직 X 그 함수가 몇 번 호출되느냐 인거에요.

자 여러분 이 함수의 main 로직이 뭐죠?

이 함수의 main 로직은 정말 간단해요. cnt++ 하고 출력하는 상수 시간의 시간 복잡도를 가지는 로직이에요.

그러면 여기서 main 로직이 O(1)이 되겠죠?

그럼 여기서 질문, 만약에 이 함수의 main 로직이 이런거에요.

이러면 이 함수의 main 로직은 O(N)이 되죠.

다시 지우고, solve 라는 재귀함수는 간단해요.

매개변수 N을 받아서 N을 마이너스 1, 하나씩 줄여갑니다. 그리고 solve 라는 함수 하나마다 3번 호출하는 함수구요. 만약에 solve에 전달되는 N이  0이 되면 return 하는 기저사례를 갖고있는 재귀함수에요.

몇 번 호출될까요?

만약에 이런 게 코딩 인터뷰나 알고리즘 문제로 등장한다고 했을 때 이거 몇번 호출될지 잘 모르겠잖아요. 그럼 바로 테스팅을 해보세요.

자 제가 3을 입력해볼게요.

그럼 cnt가 40번이 출력이 되는걸 볼 수가 있어요.

n = 3일 때, 40번 호출된 거예요. 도식화를 시켜볼게요.

그 전에 재귀함수는 뭐라고요? 기억해주세요. 재귀함수는 main 로직 X 몇 번 함수 호출되는지 입니다.

이제 도식화를 할건데, solve 라는 이름이 기니까 go 라고 이름을 잠시 바꿔볼게요.

이렇게 N이 3, 2, 1로 내려가면서 함수 하나마다 3갈래로 나눠집니다.

그래서 등비수열의 합으로 40이 나오는 걸 볼 수 있죠.

그래서 등비수열의 합 공식을 대입하면 이렇게 나옵니다. 사실 정확히는 3^(n+1) 입니다. 어차피 상수인자는 날라갈 것이므로 이렇게 나오긴 합니다. n = 3 대입하면 40이 나옵니다.

그래서 빅오 표기법으로 하면 O(3^n)이 됩니다.

따라서, O(1) * O(3^n) 이므로 그냥 O(3^n)이 됩니다.

이렇게 된 거죠.

'아니 수학적 개념이 나오니까 너무 어려워요' 이렇게 할 수가 있어요. 그럼 제가 팁 하나 드릴게요.

자 함수 하나당 만약에 4번 호출하게 돼요. 그러면 main 로직 말고, 이 함수가 호출되는 시간 복잡도는 4의 n승이에요.

만약 함수 하나당 이 함수가 2번 호출돼요. 그러면 2의 n승이 되는 거예요.

만약 이러면 7의 n승이겠죠.

참고로 읽어보세요.