임의의 배열에서

가장 작은 것을 찾는건 O(N)이지. (N은 배열의 길이)

 

 

 

그럼 k번째 작은 것을 찾는건 어떻게 할까?

가장 작은 것을 찾는 걸 k번 하면 찾을 수 있긴 한데, 이 방법은 빠르지 않음.

 

효율적인 방법은?

사실 k가 N에 가까우면 n-k + 1번째로 큰 숫자를 찾으면 되는 건데,

k 가 N/2일때, 즉 k번째 작은 것을 찾아야 한다면 O(N^2/2)가 되므로, O(N^2)임.

 

이 방법 제외하고 O(N)에 찾는 방법이 있음.

 

사실 거의 모든 분야의 거의 모든 방법이 보통 사람들이 그냥 막 쓰는 방법보다 효율적인(점근적으로) 방법이 있음.

 

어셈블리 막 써서 빠른 소프트웨어를 만드는 게 아니라, 대부분 알고리즘을 개선하는 방법으로 소프트웨어를 빠르게 만듬.