인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도
작성
·
1.1K
1
계산하는법을 몰라서 질문드립니다.
[심화] 시간복잡도 강의에서
예시로 알려주심 Two sum 에서요
제약조건 중에 아래와 같은 것이 있었는데요
O(nlogn)에 10의 9승을 대입해도 10의8승이 넘어간다고 하셨는데
nlogn에 10의9승을 n에 대입하고 나서
계산을 어떻게해야지 모르겠습니다
10의 8승이 넘어가는지 어떻게 알 수 있나요??
해당부분에 대해서 검색을 해봤는데
나오지가 않네요ㅜㅜ
답변 1
1
안녕하세요 민지님. 제가 친절하지 못했네요 ㅜㅜ
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이라고 생각하셔도 됩니다.
어림추산! 대강만 계산하면 돼요
혹시 질문에 대한 답이 됐을까요~?
더 궁금한 점이 있으시면 언제든 질문 주세요 :)
친절한 설명 감사합니다
시간복잡도 대강?만 알면 되는것은 알고있었지만
수학적인 부분이라 검색으로 혼자 해결하려고 했습니다
근데 이렇게 대강(?) 계산하는 방법을 설명해주는 곳이 아무리찾아도 없었습니다
그래서 여기다 질문하게되었습니다.
덕분에 이해되었습니다!! 오래전부터 궁금했던 부분이 해결되었습니다
감사합니다😃