시간복잡도

Question

계산하는법을 몰라서 질문드립니다.   [심화] 시간복잡도 강의에서 예시로 알려주심 Two sum 에서요 제약조건 중에 아래와 같은 것이 있었는데요 O(nlogn)에 10의 9승을 대입해도 10의8승이 넘어간다고 하셨는데 nlogn에 10의9승을 n에 대입하고 나서 계산을 어떻게해야지 모르겠습니다 10의 8승이 넘어가는지 어떻게 알 수 있나요?? 해당부분에 대해서 검색을 해봤는데 나오지가 않네요ㅜㅜ

nossi · Answer

안녕하세요 민지님. 제가 친절하지 못했네요 ㅜㅜ 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이라고 생각하셔도 됩니다. 어림추산! 대강만 계산하면 돼요   혹시 질문에 대한 답이 됐을까요~? 더 궁금한 점이 있으시면 언제든 질문 주세요 :)