1주차 개념 #5-1. 문제로 연습하는 시간복잡도 Q3

1주차 개념 #5-1. 문제로 연습하는 시간복잡도 Q3

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

이 코드 go 라는 재귀함수가 들어가 있네요. '아니 선생님 재귀함수를 갑자기 어떻게 풉니까! for 반복문도 어려운데'

여러분 어려울 땐 생각만 하지 말고 뭐 하라고요? 디버깅을 하십시오.

그러니까 사실 시간 복잡도는 단순해요.

시간 복잡도는 몇 번 반복되느냐, 어떠한 로직 자체가 몇 번 일어났냐라는 걸 판단해서 그걸 식으로 만들어가지고 빅오 표기법으로 표현하는 거예요.

그러면 자 이거는 반복문이 아니죠?

대신 이런 식으로 재귀함수로서 go 라는 함수가 이렇게 호출이 되고 있죠? 그러면 이 go라는 함수가 몇 번 호출됐는지가 이 코드의 시간복잡도를 결정되는 핵심이겠네요.

자 그럼 어떻게 하면 돼요?

cnt 만들고 몇 번 호출 됐나 하고 이런 식으로 디버깅 코드를 작성하는 겁니다.

생각만 하지 말고 디버깅하라!

실행을 해보면,

이렇게 나옵니다. 로직 자체는 단순한 로직이에요. go란 함수를 mid를 기반으로 둘로 나눠요. 그러고 sum을 구하는 문제인데 이 함수가 몇 번 호출 됐냐, n이 10일 때 cnt가 19가 나와요.

n이 5일 때는 9가 나오네요.

이거를 그림으로 한번 그려볼게요. 우리 앞서서 1번 할 때도 동일한데 cnt로 디버깅을 하시고요. 그리고 그림을 그리거나 손코딩을 통해서 하라고 말씀을 드렸죠.

여러분 그냥 하시면 이해가 됩니다.

n이 5일 때를 그려보면,

이렇게 됩니다. 재귀함수는 항상 기저사례가 있어야 된다 라고 설명을 드렸죠.

l과 r이 같으면 그냥 return a[l]; 이라고 했죠.

자 몇 번 호출 됐어요?

n이 5일 때 9번이네요. 그리고 이런 식으로 했을 때 지금 n이 10일 때 19번이네요.

혹시 시간복잡도가 2n-1 아닌가? 의심이 가죠.

우리가 이렇게 cnt를 해보고 손코딩을 해보니까 시간 복잡도가 2n-1인 것 같다. 이런 식으로 관계를 찾을 수가 있었죠. 그럼 테스팅을 해보는 거예요.

n = 20일 때, 39니까 예상한게 맞구나! 이 코드의 시간복잡도는 2n-1 임을 알 수가 있죠.

cnt로 이 함수가 몇 번 노출됐는지 찍어보면 되는거죠. 여러분 시간복잡도는 어떤 로직? go 함수에서 main 로직은 정말 mid로 나눠가지고 + 하는 로직밖에 없습니다.

제가 이런 플러스나 나누기는 뭐라고 했죠? 상수 시간의 복잡도를 가지는 로직이라고 말씀을 드렸죠.

그러면 이 go 라는 함수가 몇 번 반복됐냐? 몇 번 호출됐냐? 라는 게 중요한 건데, 함수호출이 좀 어려울 수도 있으니까 디버깅을 해보시라는 겁니다.

그리고 그림으로 이런 식으로 파생돼서 9번이 호출되는 거라는 걸 알았죠. 그리고 나서 n을 바꿔가면서 cnt 값을 보니까 2n-1 관계의 시간 복잡도를 알 수가 있었습니다.

자 그러면 이거를 빅오 표기법으로 나타내면, 가장 큰 영향을 주는 항은 두 가지 항 중에서 2n이죠. 그리고 상수인자 날려버리니까, 시간 복잡도는 O(n) 입니다.

여러분 생각만 하지 말고 디버깅을 하시면 됩니다.