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

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

자 오늘은 조금 어려운 거를 해보려고 해요.

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

solve라는 함수를 보면, 입력 n을 받아 가지고 i는 0보다 클 때까지 루프를 돌립니다.

여기서 이 부분은 상수니까 이 루프가 몇 번 반복되는가가 이 알고리즘의 핵심이다, 즉 이 알고리즘의 시간 복잡도를 측정하는 핵심이다. 라는 걸 알 수가 있죠.

그럼 이게 몇 번 반복될까 라는 거를 오늘 차근차근 얘기를 해보도록 할 텐데,

로그는요 지수함수의 역함수구요. 로그는 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타낸다고 볼 수가 있습니다.

자 뭐냐면 차근차근 설명을 해볼게요.

밑이 2인데, 이 밑을 몇 번 곱해야 x가 되냐 라는 거를 log2(x)로 표현을 해요.

여러분 앞으로 알고리즘 문제 풀 때 시간 복잡도 측정한다 라고 했을 때 log(n) 이런 게 나올 거에요.

근데 보통은 밑이 2인게 축약된 걸겁니다.

자 그러면 또 설명을 해보도록 할게요.

이렇게 되죠. 근데 나누는 건 사실 곱하기와 똑같죠?

자 이런 횟수를 뭐라고 하죠? log2(32) 라고 할 수 있는 거예요.

자 그러면 다시 코드를 볼게요.

i를 계속해서 2로 나누죠? 다시 말하면 i에다가 2를 계속 곱해서 N을 만드는 것, 즉 log2(N)과 똑같죠.

'선생님 이해가 안돼요!' 이해가 안되면 뭐 하면 된다? 디버깅을 하면 된다.

cnt 해서 출력을 해볼게요.

n이 32일 때, 6이 나오고 n이 16일 때 5가 나왔죠.

'아 log2(n) + 1 이구나' 라는 걸 유추할 수 있죠.

물론 정확히 증명을 하려면 여러가지가 있겠지만, 우리가 코딩 테스트나 알고리즘 문제를 풀 때는 이렇게 균형학적 증명 이런 거를 할 시간이 없어요. 그래서 대략적으로 이렇게 되는구나 라고 해서 들어가시는 거예요.

이 코드를 봤을 때, i를 계속해서 2로 나누니까 이 알고리즘에 들어가는 횟수가 log2(n)이라는 것을 알 수가 있었죠.

이제 이거를 빅오 표기법으로 나타내면 어떻게 되죠?

O(1) < O(logN) 이니까 O(logN) 입니다. + 1은 날려버리고요. O(log2N)도 맞는 말입니다.