각 DS의 기능별 시간복잡도와 공간복잡도

정렬알고리즘의 case별 효율성과 공간복잡도

http://bigocheatsheet.com/ 에서 선명하게 확인 할 수 있다.

Data Structures

Array는 접근시간이 짧다.
Stack, Queue는 구현이 쉽고 Insert, Delete의 소요시간이 작다.
Hash table은 평균적으로 Search, Insert, Delete의 속도가 무지 빠르다.
AVL Tree는 Worst Case 에서도 모든 기능에 대해 무난한 성능을 보여줄 수 있다. (하지만 구현이 좀 어렵다)

Sorting Algorithms

Insertionsort, Heapsort 와 k가 들어가는 Radix Sort종류만 보면 된다.
Insertionsort는 partially sorted 된 array에 대해 정렬을 O(n)수준으로 빠르게 할 수 있다. 주로 짧은 array를 정렬할때 쓰면 좋다.
Heapsort의 장점은 무난한 속도(nlogn)와 작은 Space Complexity(O(1))이다.
Bucketsort와 Countingsort의 경우 O(n+k) 급의 엄청난 속도를 보여주나 Space Complexity가 각각과 O(n), O(k)이다.
Radixsort는 Countingsort와 비슷하게 쓰이는데 string 이나 정수의 고정된 길이만큼 반복한다. 그래서 O(nk) 성능을 보인다.
각각의 알고리즘은 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 여기서 여러번 천천히 보면 그 논리를 이해하기 쉽다.
Countingsort 와 Radixsort 모두 한번 씩 보는것을 추천한다.
n, k, 저장공간을 고려해서 어떤 sort을 이용할지 정하면 된다.

Python, Java, Android의 default sorting algorithm

문득 파이썬에서 기본으로 쓰이는 sort는 어떤 sort일까 궁금해졌다.
찾아봤더니 hybrid stable sorting algorithm 의 하나로 Timsort는 쓴다고 한다. 무려 2002년에 개발된 알고리즘이니 굉장히 신선한 알고리즘이다.
여기서 stable은 중복된 value가 있는 array는 중복값 순서가 sort했을 때도 보존되는 특성을 말한다.
Insertion sort의 중요성을 이제까지는 몰랐는데 Timsort을 알고나서 굉장히 많이 쓰이는 정렬 알고리즘임을 깨달았다.
무조건 average case에 대해서 정렬 알고리즘의 성능평가를 해야 한다고 생각했는데 어리석었다…
현실 세계에서 sorting시 성능이 좋게 최적화한것이 Timsort인데 그만큼 현실에서는 길이가 짧고도 어느정도 정렬된 array를 sort하는 경우가 많기 때문에
Insertion sort를 자주 활용한다.