computational complexity : The Sorting Problem(1)

* 정렬 알고리즘은 시간복잡도가 세타(n)이 될 수 없다.

 

lower bound를 찾아서 이것보다 낮아질 수 없음을 보이기
-> computational complexity analysis

 

 

* key값의 비교만으로 정렬하기

예)

lower bound : n lg n

 

 

 Insertion 정렬

: 이미 정렬된 배열에 원소 하나씩 추가하며 정렬하는 알고리즘

 

자기보다 작은 원소를 발견할 떄까지 앞으로 보내고 앞 원소는 뒤로 이동

 

 

<수도 코드>

 

Worst case 시간 복잡도:

Basic Operation: s[j]와 x 비교

Input Size: n(key의 개수)

->  역순으로 정렬되어있을 때 worst case가 발생한다.

-> 이 때 원소 i마다 i-1번의 비교가 발생한다. (2<=i<=n)

 

 

Average Case 시간복잡도: 

슬롯 k(1<=k<=i)에 x를 배치할 확률은 모든 k에 대하여 동일하므로 

주어진 i에 대해 x를 삽입하는데 필요한 평균 비교횟수는

->

->

 

 

 

Lower Bounds for Algorithms that remove at
most one inversion per comparison

 

* Inversion: 잘못된 순서로 있는 키의 쌍

예) 

-> 비교 한번에 기껏해야 inversion 1개를 없앤다. 

= remove at most one inversion per comparison

 

 

* worst case일때 lower bound : 적어도 n(n-1)/2번 key의 비교

 

* Average case일때 lower bound 구하기

 

-> n개의 원소가 배치되어있는 경우의 수는 n!

평균 inversion 개수 

=

만약 k개의 inversion을 갖는 순열이있다면: inversion: k개

그것을 transpose하면 C(n,2)-k개의 inversion이 생긴다 : inversion이 아닌 것: k개

* C(n,2): 전체쌍

 

총 n!이므로 쌍은 n!/2개

쌍마다 inversion의 개수는 c(n,2)개

 

그러므로 평균 inversion 개수는

따라서 Average case일때 lower bound는 n(n-1) /4