질문) 시간복잡도중 nlogn이 이해가 안됩니다.

[익명(58.227)]

n은 비례해서 가는거고 

logn은 이진탐색같은 경우라 바로 이해가 가는데,(반의반의반의반.. 이런식으로 시간이 지날수록 확 줄어드니) 

nlogn은 도대체 뭡니까?? 

[?(121.165)]

뭐긴 뭐야 log n 을 n 번 하는거지

[익명(58.227)]

이진탐색을 여러개를 하는경우 인가요?

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(58.227)]

nlogn이 logn이 여러개 있는경우인데 그런 구체적인 예시가 있을까요?

[나트륨찡(alphauri)]

1+2+3+4+5+...+logn은 O( nlogn )맞다 ㅇㅅㅇ

[나트륨찡(alphauri)]

개별 n개에 대해 각자의 노드가 logn이 있는 거지

[나트륨찡(alphauri)]

위덧셈은 개별 노드에 대해 1,2,3,4,5,...,logn인 거고

[익명(58.227)]

어렵군요..

[나트륨찡(alphauri)]

결국 노드를 전부 더하니 nlogn이 나오는 거지

[나트륨찡(alphauri)]

logn안하고 이 덧셈 구하는 경우도 간혹 있는데 결론은 수학작으로 O(nlogn)이야 logxdx가 xlogx-x=x(logx-1)=O(xlogx)임

[나트륨찡(alphauri)]

내가 잘못 생각했다ㅜㅜ log1+log2+log3+...+logn이게 nlogn임

[고양이발(nye7005)]

퀵소트 - dc App

[익명(58.227)]

위에 질문 한번 봐주실수있나요?

[고양이발(nye7005)]

무슨질문 - dc App

[익명(58.227)]

https://gall.dcinside.com/board/view/?id=programming&no=1372918&_rk=urT&page=1

[개발자(220.127)]

Merge Sort 생각해봐. 깊이는 log N 인데, 밑변은 N 이잖아. 그럼 넓이가 비용이니 N log N

[익명(58.227)]

아 뭔가 알것같기도