1주차 개념 #5-2. 문제로 연습하는 시간복잡도 Q3 점화식 설명

1주차 개념 #5-2. 문제로 연습하는 시간복잡도 Q3 점화식 설명

저희가 앞선 문제의 시간 복잡도를 구할 때 cnt라는 녀석을 기반으로 해서 디버깅을 했죠.

근데 이렇게 한 건 사실은 cnt를 기반으로 디버깅을 하면서 어림잡아서 한 거죠.

한 3가지를 기반으로 해서 어림 잡아서 시간 복잡도가 뭐뭐이다. 하면서 이렇게 계산을 한 거예요.

근데 사실은 정석적으로 얘기를 하면 이러한 걸(cnt, 디버깅) 기반으로 점화식을 만들어야 돼요.

점화식을 만들고 이 점화식을 기반으로 시간 복잡도를 파악을 해야 돼요.

근데 사실상 코딩 테스트를 하면서 이 점화식을 만들기라는 것은 굉장히 어려워요. 정말로 이거는 실력이 매우 뛰어난 사람 아니면 코딩 테스트를 하면서 점화식을 만들어서 시간 복잡도를 계산한다? 이거는 힘들죠.

그래서 제가 점화식을 만드는 것이 아닌, 다른 방법을 말씀을 드린 거예요.

근데 오늘은 점화식 만드는 것도 설명을 드릴게요. 사실 모든 시간 복잡도는 다 점화식을 만들 수가 있습니다.

근데 여러분 주의하실 점, 제가 이 점화식에 대해서 알려드린다고 해서 무조건 어떤 코드를 봤을 때 점화식을 기반으로 시간 복잡도를 해야된다라는 게 아니에요. 어림잡아 하셔도 됩니다.

시간이 남으면 점화식을 해보세요. 또는 면접에서 봤을 때 면접에서 시간이 넉넉하게 주어진다면 어림잡아 계산하지 말고 점화식을 기반으로 시간 복잡도로 계산해볼 생각을 하시는 거예요.

그러면 이 코드,

n = 4일 때 이렇게 호출이 되죠? 7번 호출 되죠? 1 + 2 + 4 입니다.

같은 식으로 n = 8일 때, 1 + 2 + 4 + 8 해서 15입니다.

여러분 이거 보시면 등비수열의 합이 생각이 나셔야 됩니다.

등비수열의 합 공식은 이렇죠.

여기서 초항은 1이고, 등비는 2죠.

그런데 몇번 반복되고 있어요? n = 8일 때 4번, n = 4일 때 3번,

log2(n) + 1 인거죠.

그럼 지금 식이 이렇게 됩니다.

식을 정리하면 2n - 1이 나옵니다. 그래서 이 코드의 시간 복잡도가 2n-1이다라는 거예요. 그런데 이렇게 생각해내는 것은 어렵기 때문에 코딩 테스트를 보면서 이런 식으로 점화식을 만들고 시간 복잡도를 하기가 좀 어려워요.

근데 정석으로 풀려면 이런 식으로 해야 된다라는 것을 참고용으로 말씀을 드린 거고요. 시간이 남거나, 조금 더 정확하게 하고 싶다라는 분들은 이런 식으로 점화식을 해서 하시는 것도 좋다라고 생각을 합니다.