질문) 찾아보니 퀵소트가 nlogn이라는데

[익명(58.227)]

예를들어 1~~100 까지 있을때 

이를 1~20 , 21~40, 41~60, 61~80, 81~100 이렇게 5개로 나누어서 각각을 이진탐색하면 

이경우 시간복잡도가 nlogn이 되는건가요? 

[나트륨찡(alphauri)]

퀵소트 O(n^2)이야 그거 평균이 O(nlogn)인데 0.0001퍼센트의 확률로 O(n^2) 걸려서 서버 다운되는 원인임

[익명(58.227)]

헉 그런가요

[나트륨찡(alphauri)]

백만개 되면 백만 나누기 자릿수 배 만큼 더 느려서 10만배 더 느려

[나트륨찡(alphauri)]

10만배 느린 거 잘못 걸리면 서버 다운돠는 거야

[나트륨찡(alphauri)]

자릿수는 10 남짓이니까 백만나누기 10 돼서 O(nlogn)보다 십만배 더 느림

[익명(58.227)]

감사합니다

[익명(211.209)]

https://haeulnam.github.io/algorithm/2019/02/20/07-QuickSort-Randomized/

[익명(58.227)]

[흔한인간(211.179)]

흔히 머지를 쓰지

[익명(58.227)]

[고양이발(nye7005)]

단순한 이중루프로 따지면 for(i =0; i < n; i++) for (j= 1; j <= n; j *= 2) 이게 nlogn이라고 볼 수 있지 - dc App