[알고리즘] 알고리즘 설계와 분석의 기초

1. 몇 가지 기초 사항들

 알고리즘 분석의 필요성

- 어떤 알고리즘을 설계하고 나면 이 알고리즘이 자원(보통 소요시간)을 얼마나 소모하는지 분석해야 할 때가 많음.

- 시간의 분석은 최악의 경우와 평균적인 경우에 대한 분석이 대표적임.

- 시간 분석을 하면 알고리즘이 어느 정도의 입력에서 어느 정도의 시간이 걸리는지 미리 짐작할 수 있음.

 

알고리즘의 수행 시간

- 알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현함.

- 입력의 크기 예 )

정렬의 경우 - 정렬하고자 하는 개체의 수

도시 간 최단 거리 구하는 경우 - 도시의 총수와 도시 간 간선(도로)의 총수

계승을 구하는 경우 - 계승치를 구하고자 하는 자연수의 크기

 

입력의 크기가 n인 경우에 간단한 연산으로 계산할 수 있는 알고리즘의 예

sample1 (A[],n)
{
    k = n/2;
    return A[k];
}

- 입력 배열의 크기 n에 상관없이 일정한 시간(상수 시간)이 소요됨.

 

sample2 (A[], n)
{
    sum <- 0;
    for i <- 1 to n
        sum <-sum + A[i];
    return sum;
}

- 배열 A[1 ~ n]의 모든 원소를 더하는 알고리즘. for 루프를 제외한 나머지 부분은 상수 시간이 소요되므로 for 루프가 시간을 지배함. for 루프는 n번 반복되고, for루프 관련 수행시간은 n에 비례하게 됨

- 따라서 알고리즘의 수행시간은 n에 비례함.

 

sample3 (A[], n)
{
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <-sum + A[i] * A[j];
    
    return sum;
}

- 배열 A[1 ~ n]의 모든 원소 쌍을 곱한 합을 구하는 알고리즘. for 루프가 총 n * n = n²번 반복되고 각 루프에서는 상수 시간 작업이 수행됨.

- 따라서 알고리즘의 수행시간은 n²에 비례함.

 

sample4 (A[], n)
{
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n {
           ① k <- A[1~n]에서 임의로 [n/2]개를 뽑을때 이들 중 최댓값;
                sum <- sum + k;
        }
    return sum;
}

- for 루프를 n²번 반복하면서 매번 배열에서 반을 임의로 뽑아 그중 최댓값을 계속 더하는 알고리즘임.

- 크기가 n인 배열에서 [n/2]개를 뽑으면서 이들 중 최댓값을 구하는 것은 n/2에 비례하는 시간이 듦.

- 즉 ①을 수행하는 데 n에 비례하는 시간이 듦. 전체적으로 for 루프의 반복 횟수와 ①의 수행시간이 시간을 좌우하므로 총 수행시간은 n² * n = n³에 비례함.

 

sample5(A[], n )
{
    sum <- 0;
    for i <- 1 to n-1
        for j <- i + 1 to n
            ① sum <- sum + A[i] * A[j];
    return sum;
}

- A[1~n]에서 i<j인 모든 원소 쌍의 곱을 합산하는 알고리즘.

- 두 개의 for 루프가 중첩된 구조임.

- for 루프의 가장 안쪽에 있는 ①은 상수 시간이 드는 간단한 작업임.

- 따라서 for 루프의 총 반복 횟수가 수행 시간을 좌우함. 바깥 for 루프에서 i = 1일때 안쪽 for 루프가 n-1회 반복되고, 바깥 for 루프에서 i = 2일때 안쪽 for 루프가 n-2회 반복되고, ... , 마지막으로 바깥 for 루프에서 i = n-1일 때 안쪽 for 루프가 1회 반복됨.

- for 루프의 총 반복 횟수는 (n-1)+(n-2) + y + 2 + 1 = n(n-1)/2이 되어 n²에 비례함. 알고리즘의 총 수행 시간은 n²에 비례함.

 

재귀(자기호출)와 귀납적 사고

- 자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식임.

- 보통 정렬에서 자기호출의 개념이 대표적으로 사용됨.

- 자기호출을 이용하는 알고리즘의 정당성은 수학적 귀납법과 관련이 깊음.

- 수학적 귀납법이란 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해 자식에게도 결론이 옳음을 보이는 것.

- 자신보다 작은 문제에서는 이 알고리즘이 제대로 작동한다고 가정하는 것.

mergeSort(A[], p, r) // A[p ~ r]을 정렬함
{
    if ( p < r ) then {
        ① q <- (p+r)/2; // p, r의 중간 지점 계산
        ② mergeSort(A,p,q); // 전반부 정렬
        ③ mergeSort(A,q+1,r); // 후반부 정렬
        ④ merge(A,p,q,r); // 병합
    }
}

merge(A[],p,q,r)
{
    정렬되어 있는 두 배열 A[p~q]와 A[q+1 ~ r]을 합쳐
    정렬된 하나의 배열 A[p ~ r]을 만듦.
}

- ① : 정렬하고자 하는 배열의 중간 지접을 계산해 전체 배열을 이등분함.
- ②③ : 이등분된 두 배열을 각각 재귀적으로 정렬함.
- ④ : 이렇게 정렬된 두 배열을 합쳐서 하나의 정렬된 배열을 만듦.

 

알고리즘으로 어떤 문제를 푸는가

1. 자동차에서 사용하는 내비게이션에서 두 지점 간의 최단 경로나 최단 시간이 걸리는 경로를 찾는 것.

2. 인터넷에서 원하는 검색의 결과를 최대한 빨리, 최대한 만족스럽게 제공하는 것.

3. 회사에서 매달 사용자에게 보내는 우편이나 이메일로 통보하는 것. ( 고객 정렬 )

2. 점근적 표기

- 알고리즘의 수행 시간은 항상 입력의 크기가 충분히 클 때 분석함. 즉 점근적 분석을 함.

- 고등학교에서 배운 lim(n→∞)를 이용한 분석이 점근적 분석의 한 예

 

θ-표기법

 - 알고리즘의 소요 시간이 입력의 크기 n에 대해 θ(n²)이라면 대략 n²에 비례하는 시간이 소요됨을 뜻함.

- θ( f(n) )은 점근적 증가율이 f(n)과 일치하는 모든 함수의 집합임.

- θ-표기는 집합으로 정의 되므로 n² + 3 ∈ θ(n²)으로 쓰는 것이 맞지만 보통 n² + 3 = θ(n²)으로 사용함.

- 5n² = θ(n²)에서 =는 ∈의 대신이므로 θ(n²) = 5n²과 같이 표현하면 안 됨.

 

O-표기법

- 알고리즘의 소요 시간이 입력의 크기 n에 대해 O(n²)이라면 기껏해야 n²에 비례하는 시간이 소요됨을 뜻함.

- O( f(n) )은 점근적 증가율이 f(n)을 넘지 않는 모든 함수의 집합임.

- O( f(n) )은 최고차항의 차수가 f(n)와 일치하거나 더 작은 함수의 집합임.

 

Ω-표기법

- 알고리즘의 소요 시간이 입력의 크기 n에 대해 Ω(n²)이라면 적어도 n²에 비례하는 시간이 소요됨을 뜻함.

- O( f(n) )은 점근적 증가율이 적어도 f(n)이 되는 모든 함수의 집합임.

- O( f(n) )은 최고차항의 차수가 f(n)와 일치하거나 더 큰 함수의 집합임.

​