졸리고 귀찮아서 깊은 얘기는 안하고....

알고리즘의 성능을 평가한다고 한다면
아주 일반적으로는 평균시간복잡도를 가지고 비교함 ㅇㅇ
Quicksort를 O(n log n)이라고 하는 이유는 여기에 있음.
사실 어지간히 "빠른" 알고리즘들은 보통 O(n log n)임
(Radix sort는 예외. 메모리 사용량이 지존이지. 시간복잡도와 더불어 공간복잡도도 중요한 요소라는)

그리고 그 다음 일반적으로 쓰이는게 worst-case 시간복잡도.
연산에 deadline이 걸린 곳에서는 이쪽이 평균보다 더 중요함.
참고로 merge sort 같은건 최악이 O (n log n)임.

그리고 amortized computational complexity라는게 있는데
이거는 모든 데이터셋이 균등하게 발생한다고 가정했을 때의 시간 복잡도.
실제보단 이론적인 곳에서 주로 쓰임.
더 이상의 자세한 설명은 생략한다.

참고로 시간복잡도 분석을 할 때의 약간의 주의점은
1) 비이론적인 부분(메모리 접근 횟수, IO 횟수, cache miss rate 등) 또한 성능에 중요한 요소임

(NOTE: 이걸 쪼끔더 이론적으로 설명하자면...
빅오의 formal definition은 다음과 같다능
f(n) = O(g(n)) ⇔ ∃k>0, ∃n0, ∀n>n0, |f(n)| ≤ |k g(n)|
여기보면 임의의 양수 k가 있는데, 알고리즘마다 다르고, implementation마다 또 다르다는.
헌데 이 k값의 크기와는 상관 없이, 함수의 시간 값이 g(n)에 의해 dominated 된다면
그 함수는 무조건 O(g(n))이라고 불림.
가끔 이 k 값의 차이로 인해 체감 가능할 정도의 시간 차이가 발생하기도 한다능.
알아두면 일생에 한 두번쯤은 유용할지도 [...])

2) N에 따라 성능의 순서가 뒤바뀔 수 있음.
예를 들면 O(n^1.1)하고 O(n log n)을 비교하면,
초반엔 O(n log n)이 우세하지만, 뒤에가면 O(n^1.1)이 우세하다는.

3)...을 쓰려고 했는데 기억안나 ㅁㄴㅇㄹ
여기서 끝마침