퀵소트: 

평균 nlogn, 

최악 n^2(데이터가 이미 거의 정렬되어 있는 경우)



머지소트: 

평균: nlogn보장

단점: 메모리 비효율적이라는 문제-> 힙소트로 해결



힙소트:

일단 데이터를 가지고 힙구조를 만들어야함. 이 부분의 복잡도 == NlogN

그리고, 루트의 값을 맨 뒤로 보내면서, 보낸 값을 제외하고 다시 힙을 만드는 비용이 logN. 이걸 N번 반복하니까 NlogN

결국 합치면 총 시간 복잡도는 NlogN이 된다.

장점: 메모리 효율적.


+ Recent posts