[알고리즘] problem Analysis in Insertion Sort

Two Types of Complexity Analysis

Algorithm Analysis

: 효율적인 알고리즘을 찾기 위한 접근법

-> time complexity & space complexity

problem Analysis

: 좀 더 본질적인 문제의 복잡성에 대한 분석

-> matrix multiplication의 경우 n^3이 되는 경우, n^2.81(스트라센) 아무튼 이런저런 방식이 있음

-> 계산 복잡도에 대한 분석을 해보자? (computatuinal complexity analysis)

Computational Complexity

Objective

Ω(f(n))에 대해 Θ(f(n))을 개발하는 방법?

-> 하지만 문제의 하한보다 낮은 알고리즘을 개발하는 것은 불가능!!

ex. sorting problem

- Exchange sort : Θ(n^2)

- Merge sort:  Θ(n^2) (n lg n)

- sorting problem의 하한은 Ω (n lg n)
- 다행히 정렬 문제의 하한선을 건드리는 알고리즘을 찾음! -> 더 작은 lower bound는 어떻게 찾을 수 있을까?

Insertion Sort

 

Insertion Sort : 정리 된 부분과 아닌 부분으로 나눠서 정렬

Problem

내림차순으로 정리되지 않은 n개의 키 값들

Input

- 양의 정수 n

- 1부터 n까지 키 값들을 담고 있는 배열 S

Output

내림차순으로 정리된 배열 S

void insertionsort(int n, keytype S[]) {
	index i, j;
    keytype x;
    for(i = 2; i <= n; i++){ //2번째부터 끝까지
    	x = S[i]; //지금 확인할 값
        j = i - 1; //이미 다 정리된 값들 중 가장 큰 값?
        while(j > 0 && S[j] > x) { //x보다 큰 값이 나올 때 까지 내려가기
        	S[j + 1] = s[j];
            j--;
        }
        S[j + 1] = x;
    }
}

 

Inserting Sort Algorithm Analysis

Worst case Time Complexity Analysis

 

모든 경우에서 i - 1번 하는 경우

 

 

 

Average case Time Complexity Analysis

아무튼 i개 중에 하나니까.. 1/i? 아무튼 저런 복잡도를 갖는다..~

---

Selection Sort

: 가장 작은걸 맨 앞에, 2번째 작은건 2번째 ..

Problem

내림차순으로 정리되지 않은 n개의 키 값들

Input

- 양의 정수 n

- 1부터 n까지 키 값들을 담고 있는 배열 S

Output

내림차순으로 정리된 배열 S

void selectionsort(int n, keytype S[]) {
	index i, j, smallest;
    for (i = 1; i <= n - 1; i++) { //1부터 끝나기 하나 전 까지
    	smallest = i; //현재 검사하는거랑 비교할거임
        for(j = i + 1; j <= n; j++) { // 전부 다 돌아보면서 찾음
        	if(S[j] < S[smallest]) //더 작은걸 찾으면
            	smallest = j;
            exchange S[i] and S[smallest]; //바꿔주기
        }
    }
}

Selection Sort Algorithm Analysis

Every case Time Complexity Analysis

아무래도 그렇게 되겠죠 음음

근데 여러가지 방법을 해봤는데 결과적으로 비슷하더라

다 비슷하구먼

Lower Bounds for Algorithms that Remove at Most one inversion per comparison

아무튼 한 번 비교할 때 하나밖에 알 수 없다는거!

- [1, 2, 3, ..., n]을 나열하는 방법은 n! 개

- 만약 i < j 인데 ki > kj 라면 inversion

worst case

[n, n - 1, ... , 2, 1] 반대로 정렬된 정렬을 정렬하는 경우

-> 전부 살펴야하기 때문에 n(n-1)/2

Average case

P= [k1, k2,..., kn] //이건 정렬된거?

PT= [kn,..., k2, k1] //이건 정렬 안된거?
- 임의의 쌍(s, r)은 항상 P 또는 PT에 속한다. //아무래도 그렇지
- In other words, I(P) + I(PT) = ½ n(n-1) .
- 따라서 평균적으로 ¼ n(n-1)이 존재한다

 

그렇기 하네요 대략적으로 절반이다~라는건가?

---

강의 대충 들어서 잘 모르겠으니 조만간 다시 하도록 하죠

아마 내일쯤