목록정렬 (1)

Heap/Radix/Quick Sort에 대하여

Quick Sort : O(NlogN), 최악의 경우 O(N^2)을 보장하는 소팅. Heap Sort : O(NlogN)을 보장하는 소팅 Radix Sort : O(dN)을 보장하는 소팅(자리수) 으로 이론적으로만 알고있어서 오늘 구현해본결과, 속도차이가 그닥 나지않음을 발견했다 알고리즘공부하면서 Big-O표기법에 대해 항상 께림직했던게, 결국 Big-O는 수학에서 말하는 N이 충분히 큰 경우(sufficiently large) 계수는 무시할 수 있기에, 계수를 제외한 값을 표현해준다는 것이다. Quick Sort는 별 할말이없다. 워낙 유명한 소팅이라.. 굳이 한마디 하자면 pivot을 그지같이 잡거나 해서 최악의 경우 N^2이라곤 하지만, 생각보다?(이름만큼?) 속도가 빠르다 Heap Sort Hea..
Algorithm/그밖에2 2016. 8. 15. 21:59
이전 Prev 1 Next 다음