[알고리즘 문제해결 전략]4장. 알고리즘의 시간 복잡도 분석

Preview

---

알고리즘의 시간 복잡도는 알고리즘의 수행 시간을 반복문이 수행되는 횟수로 측정한다

--> 주로 입력되는 크기에 대한 함수로 표현된다.

1. 선형 시간 알고리즘

2. 선형 이하 시간 알고리즘

3. 지수시간 알고리즘

4. 시간 복잡도

5. 수행시간 어림 짐작하기

6. 계산 복잡도 클래스

1. 선형 시간 알고리즘

---

입력의 크기에 대비해 걸리는 시간을 그래프로 그려보면 직선이 되는 알고리즘

EX>

매달 N개의 측정치가 주어질 때, 매달 M달간의 평균을 구해라.

ⅰ) 마구잡이로 풀어보기

 

vector<double> GetAvg(const vector<double>& A, int M){
    vector<double> ret;
    int N = A.size();
    for(int i = M - 1; i < N; ++i){
        double partial_sum = 0;
        for(int j = 0;  j < M; j++)
            partial_sum += A[i-j];
        ret.push_back(partial_sum/M);
    } 
    return ret;
}

[코드 1. 마구잡이로 풀어보기]

 다음과 같이 모든 지점에서 M번의 수를 더해서 구하는 방식으로 알고리즘을 구성한다면, 

반복문은 M*(N-M+1)번 반복된다.

 여기서 만약 N과 M이 매우 커진다면 반복문은 몇 억번을 반복되는 경우도 생깁니다. 이를 좀 더 빠른 시간내에 해결할 수 있는 방법에 대해서 알아봅시다.

ⅱ) 선형시간에 대해서 문제 풀어보기

vector<double> GetAvg_linear(const vector<double>& A, int M){
    vector<double> ret;
    int N = A.size();
    double partial_sum = 0;
    for(int i = 0 ; i < M-1; i++)
        partial_sum += A[i];
    for(int j = M - 1;  j < N; j++){
        partial_sum += A[i];
        ret.push_back(partial_sum/M);
        partial_sum -= A[i-M+1];
    } 
    return ret;
}

[코드 2. 선형시간에 대해서 문제풀어보기]

 위와 같이 partial_sum에 값을 더 하고 M개가 되었을 때 평균을 구해 넣고 partial_sum에 가장 앞에 있는 값을 빼고 다시 최근에 있는 값을 더하는 방식으로 알고리즘을 구성한다면 N번의 반복이 생깁니다.

2. 선형 이하 시간 알고리즘

---

입력의 크기가 커지는 것보다 수행시간이 느리게 증가하는 알고리즘

EX>

ⅰ) 이진 탐색

 

 binsearch(A[], x) = 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 때, A[i-1]＜ x ≤ A[i]인 i를 반환한다. 이때 A[-1] = -∞, A[N] = ∞으로 가정한다.(N = A.size())

이진 탐색의 원리 :

[그림 1]

 배열 A가 [그림 1]과 같이 주어졌다고 하고 x= 4라고 하자.

[그림 2]

 처음에는 배열 A의 중간값 즉, mid = (0 + 7)/2 = 3, A[3]의 값과 비교를 할 것이다. A[3] = 7 ＞ x = 4 이므로 왼쪽의 값을 가지고 다시 탐색을 할 것이다.

[그림 3]

위의 그림과 같이 mid = (0 + 3) = 1 즉, A[1] = 4로서 x의 값을 찾았다. 해당 값의 인덱스인 1이 반환 될것이다.

 이처럼 이진 탐색을 하게 된다면 의 시간복잡도로 탐색을 할 것이다.

 

3. 지수 시간 알고리즘

---

입력의 크기 N이 하나 증가 할때마다 걸리는 시간이 배로 걸리는 알고리즘

**다항 시간 알고리즘? 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘

EX>

 N명의 사람들에게 요리를 대접할때, 요리판에 있는 요리수는 M개이다. 여기서 각각의 사람들은 먹지 못하는 음식이 존재한다. 이때, 가장 적은 종류의 음식으로 모든 사람이 음식을 먹을 수 있도록 하고 싶다. 총 몇개의 음식을 해야 할까?

[그림 4]

위의 문제는 [그림 4]와 같이 생각할 수 있다. 여기서 위의 그림과 같이 프로그램을 구성한다면 아래와 동일해 진다.

#define INF 987654321
 
bool canAllEat(const vector<int>& menu);
 
int M;
 
int selectFood(vector<int>& menu,int food){
    if(food == M){
        if(canAllEat(menu)) return menu.size();
        return INF;
    }
    int ret = selectFood(menu,food+1);
    menu.push_back(food);
    ret = min(ret, selectFood(menu,food+1));
    menu.pop_back();
    return ret;
}

[코드 3. selectFood]

해당 코드는 [그림 4]와 같이 각각의 음식을 선택하거나 선택하지 않을 경우 모두 음식을 먹을 수 있는지 없는지를 확인하는 코드이다. 이때, canAllEat함수에서 M*N의 시간복잡도가 생긴다고 가정하면 selectFood함수의 경우, 의 시간 복잡도를 가지게 된다.

4. 시간 복잡도

---

가장 널리 사용되는 알고리즘의 수행시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것

입력의 종류에 따라 수행시간이 달라진다.

 입력의 크기만 수행시간을 결정하는 척도는 아니다. 순차검색*알고리즘에 대하여 생각해보자. 입력의 크기가 하나 더라도, 찾고자하는 값이 어디에 있냐에 따라 수행시간이 달라진다.

**순차 검색알고리즘: 처음부터 순차적으로 하나씩 원하는 값을 탐색해나가는 알고리즘

 

 이러한 경우를 고려하기 위해 최선/최악의 경우 그리고 평균적인 경우에 대한 수행시간을 따로 계산한다.

Big-O표기법.

 알고리즘 수행시간을 나타내는 표기법이다. 간단하게 설명을 하자면 주어진 함수에서 가장 빨리 증가하는 항마을 남긴채 나머지는 다 버리는 표기법이다.

 

 N에 대한 함수 F(N)이 주어질 때, F(N) = O(g(N))이라고 표현을 한다면 이는 아래를 의미한다.

 아주 큰와 (, > 0)를 적절히 선택하면 ≤N인 모든 N에  대해

이 참이 되도록 할 수 있다.

EX>

5. 수행시간 어림짐작하기

---

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 1초당 반복문 수행 횟수가 1억()을 넘어가면 시간제한을 초과할 가능성이 크다.

6. 계산 복잡도 클래스: P, NP, NP-Complete

---

P(polynomial) : 다항시간 시간 알고리즘이 존재하는 문제들의 집합

NP(non-polynomial) : 답이 주어졌을 때 이것이 정답인지를 다항시간 내에 확인할 수 있는 문제

NP-Hard : 하나의 NP문제들을 풀수 있으면 모든 NP문제들을 풀 수 있는 문제들의 집합

NP-Complete : NP-Hard이면서 NP인 문제

7. 출처

---

[코드 1]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.95(코드 4.3)

[코드 2]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.97(코드 4.4)

[코드 3]: 프로그래밍 대회에서 배우는 알고리즘 문제 해결전략 p.103(코드 4.5)