Hyun's Wonderwall

[컴퓨터알고리즘] 1, 2장 - 알고리즘 소개, 삽입 정렬 본문

Subjects/컴퓨터알고리즘

[컴퓨터알고리즘] 1, 2장 - 알고리즘 소개, 삽입 정렬

Hyun_! 2024. 4. 24. 15:25

1단원

알고리즘 과목에서 공부할 내용

- 알고리즘 표현: 문제를 정확하고 추상적으로 정의하는 것, 알고리즘을 수도코드로 나타내는 것

- 알고리즘 유효성: 알고리즘이 옳다는 것을 증명

- 알고리즘 분석: 시, 공간 복잡도.

- 알고리즘 설계: 고전적인 알고리즘. 메타 알고리즘. 어떤 상황에 사용?

 

알고리즘이란?

- 절차의 순서. 주어진 문제에 대해, 조건 만족 위해. 입력. 출력. 자료구조와 연관.

 

알고리즘 분석

- 성능과 리소스 사용량 중요. 그외에 정확성. 간결성. 신뢰성 등..

 

왜 알고리즘과 성능을 공부?

- 확장성 이해 도와줌. 실행 가능/불가능 알수있. 성능이 가치판단의 기준이 됨. 등


2단원

Pseudocode: 알고리즘 표현을 위해 설계되었음. 컴파일되지는 않음.

 

삽입정렬 Insertion Sort

Input: a1~an 숫자

Output: a1~an (크기순서대로인) 순열.

- 작은 개수의 요소를 정렬하기 좋음.

- 제자리 정렬, 별도의 메모리공간 사용x. 시작할 때 정렬된 건 A[1], 정렬 진행할 수록 A[1...j]가 정렬됨.

- 삽입정렬은 점진적으로 정렬됨.

# pseudo code
INSERTION-SORT(A,n)
	for j ← 2 to n do
    	key ← A[j]
        i ← j - 1
        while i > 0 and A[i] > key do
        	A[i+1] ← A[i]
         	i ← i - 1
        A[i+1] = key

 

pseudo code: block이 없고 들여쓰기를 사용. = 대신 ←를 사용. 배열 인덱스 1에서 시작함.

 

루프 불변성 Loop invariants: 모든 한 루프에서 정렬이 보장됨.

 

Correctness: 어떤 일반적인 input이든간에 원하는 정확한 출력이 나와야함. 보통 수학적 귀납법

- 어떻게 증명? (1) 실제 값 넣고 추적해 증명 (2) 추상적인 (a1, ... an) 값 넣고 추적해 증명

- 반례 찾기 위해 넣어볼 수 있는 입력: (1)이미 정렬된, (2)중복된 요소들이 있는, (3)매우 작거나 큰

 

삽입 정렬의 루프 불변성과 정확성

- Claim: 매 루프에서 A[1...j-1]이 정렬된다.

- Proof: induction을 이용

 

Proof by Induction (수학적 귀납법)

- Claim: S(n) 이 모든 n>=1에 대하여 참을 증명해야 한다.

- Basis 기본 가정: n=1일 때 참임을 밝힌다

- Inductive Hypothesis 귀납가정: 임의의 n=k에 대해 참이라고 가정한다.

- Step: n=k+1에 대해 참임을 밝힌다.

 

루프 불변성을 이용해 알고리즘이 참임을 증명

1. Initialization(초기조건)

- 루프 불변성이 루프의 첫번째 반복이 시작될 때 참이다.

2. Maintenance(유지조건):

- 루프가 시작되기 전에 참이라고 가정한다.

- 그리고 (이번 루프 이후) 다음 반복 시작 전에 참이라는 것을 보인다.

3. Termination(종료조건)

- 루프가 종료할 때, 루프 불변성이 알고리즘이 옳음을 보이는 데 유용한 특성이라는 것을 보인다.

 

삽입정렬 코드

# 수도 코드
InsertionSort(A, n) {
    for j ← 2 to n do
        key ← A[j]
        i ← j - 1
        while i > 0 and A[i] > key do
            A[i+1] ← A[i]
            i ← i - 1
        A[i+1] ← key
}
// C언어, A[1]부터 시작하는 경우 (A[0] 사용 x)
void InsertionSort(int A[], int n) {
    int j, i, key;
    for (j = 2; j <= n; j++) {
        key = A[j];
        i = j - 1;
        // A[j]를 A[1..j-1]에 삽입한다
        while (i > 0 && A[i] > key) {
        	A[i+1] = A[i];
            i = i - 1;
        }
        A[i+1] = key;
    }
}

 

Initialization 초기조건

- A[1]은 정렬되어있다. 따라서 루프가 시작할 때 루프 불변성은 참이다.

Maintenance

- 루프 불변성이 j번째 반복에서 참이라고 하자.

- A[j]를 정렬된 A[1..j-1]에 삽입하는데, 루프를 하다 반복 멈추었을 때  A[j+1]=key으로 들어가므로 j+1번째 반복 전에 루프 불변성이 참이게 된다.

Termination: 종료 시점에 A[1..n]은 A의 요소들을 정렬된 순서로 갖게 된다. (증명 완)

 

Efficiency: 효율성. 

실행시간 어떻게? 연산

 

Asymptotic Analysis 점근적 분석기법

- 입력 크기 커지면 알고리즘 실행 시간도 커짐.

- 실행 시간이 입력 크기에 의존한다.

- 큰 배열-> 정렬에 더 오랜 시간. T(n): 크기 n인 입력에 걸리는 시간.

- T(n)의 growth(기울기)을 n->무한대로 갈 때 바라본다.

- size: 입력 요소의 개수.

- 실행 시간의 상한선을 본다(big O..)

 

삽입 정렬의 수행시간

- 거의 대부분 정렬된 경우 정렬 쉽다. 입력 크기 작으면 정렬 쉽다.

 

King of analyses

- Worst-case: 대부분의 경우. T(n)=아무 입력, 최대 시간

- Average-case: T(n)=모든 입력, 평균적인 시간.

- Best-case: 운이 좋은 경우.

 

삽입 정렬의 cost, time 분석

각 단계의 cost * time의 합 -> T(n)

InsertionSort(A, n) {
    for j ← 2 to n do	# c1 * n
        key ← A[j]	# c2 * (n-1)
        i ← j - 1	# c3 * (n-1)
        while i > 0 and A[i] > key do	# c4 * j=2부터 n까지 tj
            A[i+1] ← A[i]		# c5 * j=2부터 n까지 (tj-1)
            i ← i - 1			# c6 * j=2부터 n까지 (tj-1)
        A[i+1] ← key	# c7 * (n-1)
}

T(n) = c1n + c2(n-1) + c3(n-1) + c4 * j=2부터 n까지 tj + c5 * j=2부터 n까지 (tj-1) + c6 * j=2부터 n까지 (tj-1) + c7(n-1)

 

1. 최적의 경우 (이미 정렬됨)

- tj=1. T(n)=an+b. 그냥 n번의 비교를 함. 선형적.

2. 최악의 경우

- tj=j. 이러면 급수 쓰인 부분들이 모두 2차가 됨. T(n)=an^2+bn+c. 이차식 형태로 시간복잡도->상한.

3. 평균의 경우

- tj=j/2. 마찬가지로 T(n)=an^2+bn+c.

 

Theta notation

Θ(g(n)) = { f(n) : 0<= c1g(n) <= f(n) <= c2g(n) for all n>= n0 }