알고리즘의 분석

출처: 영리한 프로그래밍을 위한 알고리즘 강좌

  • 알고리즘의 자원 사용량을 분석
  • 자원이란 실행 시간, 메모리, 저장장치, 통신 등
  • 여기서는 실행시간의 분석에 대해서 다룸

시간복잡도

  • 실행시간은 실행환경에 따라 달라짐
    • 하드웨어, 운영체제, 언어, 컴파일러 등
  • 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트
  • 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
  • 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐
    • 최악의 경우 시간복잡도
    • 평균 시간복잡도

점근적 분석

  • 점근적 표기법을 사용
    • 데이터의 개수 n→∞일 때, 수행 시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법
    • Θ-표기, O-표기 등을 사용
  • 유일한 분석법도 아니고 가장 좋은 분석법도 아님
    • 다만 (상대적으로) 가장 간단하며
    • 알고리즘의 실행환경에 비의존적임
    • 그래서 가장 광범위하게 사용됨

점근적 분석의 예: 상수 시간복잡도

/*

* 입력으로 n개의 데이터가 저장된 배열 data가 주어지고,
* 그 중 n/2번째 데이터를 반환한다.

 */
int sample(int data[], int n)
{
    int k = n/2;
    return data[k];
}

n에 관계없이 상수 시간이 소요된다. 이 경우 알고리즘의 시간복잡도는 O(1)이다.

점근적 분석의 예: 선형 시간복잡도

/*

* 입력으로 n개의 데이터가 저장된 배열 data가 주어지고,
* 그 합을 구하여 반환한다.

 */
int sum(int data[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + data[i];
    return sum;
}

선형 시간복잡도를 가진다고 말하고 O(n)이라고 표기한다.

선형 시간복잡도: 순차탐색

// 배열 data에 정수 target이 있는지 검색한다.
int search(int n, int data[], int target)
{
    for (int i = 0; i < n; i++) {
        // 이 알고리즘에서 가장 자주 실행되는 문장이며,
        // 실행 횟수는 최악의 경우 n번이다.
        if (data[i] == target)
            return i;
    }
}

최악의 경우 시간복잡도는 O(n)이다.

Quadratic

/*

* 배열 x에 중복된 원소가 있는지 검사하는 함수이다.

 */
bool is_distinct(int n, int x[])
{
    for (int i = 0; i < n-1; i++)
        for (int j = i+1; j < n; j++)
        // 이 알고리즘에서 가장 자주 실행되는 문장이며,
        // 최악의 경우 실행 횟수는 n(n-1)/2 번이다.
        if (x[i] == x[j])
            return false;
    return true;
}

최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는 n(n-1)/2이다.
최악의 경우 시간복잡도는 O(n²)으로 나타낸다.

점근적 표기법

  • 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법
  • 최고차항의 차수만으로 표시 (N이 충분히 크면 상수와 계수는 의미 없음.)
  • 따라서 가장 자주 실행되는 연산 혹은 문장의 실행횟수를 고려하는 것으로 충분