시간복잡도

안녕하세요 민지님. 제가 친절하지 못했네요 ㅜㅜ

log 에대한 계산을 제가 당연하다는 듯이 넘어가서 많은 분들이 어려워 하는 것 같아요.

제가 상세히 설명 드리도록 하겠습니다!!

일단 nlogn 의 뜻은 n x logn 입니다.

그러면 logn은 어떻게 계산할까요? 이게 키포인트겠죠?

log10 = 1 이라고 생각하시면 돼요 (사실 엄밀히 들어가면 조금 다를 수 있습니다. 하지만 상관없어요. 그냥 이렇게 계산하시면 돼요)

log(10^1) = 1
log(10^2) = 2
log(10^3) = 3
log(10^4) = 4

그럼 다시 n logn을 볼까요

n = 10^9이라면

n x logn

= 10^9 x log(10^9)

= 10^9 x 9

= 9 x 10^9

=약 10 x 10^9

= 10^10 정도 되겠네요.

어림추산해도 됩니다.

logn의 계산법만 알면 nlogn은 어렵지 않을 거에요.

그럼 n = 10^4일 때는 nlogn은 대략 몇일까요?

4x10^4 정도 되겠죠. 이건 10^4이라고 생각하셔도 되고 10^5이라고 생각하셔도 됩니다.

어림추산! 대강만 계산하면 돼요

혹시 질문에 대한 답이 됐을까요~?

더 궁금한 점이 있으시면 언제든 질문 주세요 :)