점근적 분석과 시간복잡도

알고리즘의 분석

• 알고리즘의 자원사용량 분석
• 자원이란 실행시간, 메모리, 저장장치, 통신 등을 의미한다.

포스팅에서는 공간(메모리)은 실행시간에 비해 상대적으로 저비용이므로 실행시간의 분석에 대해서만 다루겠다.

• 시간복잡도

  1) 실행시간은 실행환경에 따라. 달라진다.

    - 하드웨어, 운영체제, 언어, 컴파일러 등등
  

  2) 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 하는게 더 합리적이다.

  3) 연산의 실행 횟수는 입력 데이터의 크기에 대한 함수로 표현한다.

  4) 데이터의 크기가 같더라도 실제 데이터에 따라 달라진다.

  • 예를 들어 정렬 알고리즘을 실행한다고 가정하면
    입력 데이터의 정렬 상태에 따라 연산 횟수가 달라진다.

    • 이 문제로 인해 ‘최악의 경우 시간복잡도’와 ‘평균 시간복잡도’를 사용한다.
    • ‘평균 시간복잡도’는 구하기가 쉽지 않은 경우가 많으므로 자주 사용하지 않는다.
    • ‘최악의 경우 시간복잡도’가 알고리즘 성능의 하한선을 보장 해주므로 주로 사용한다.

• 점근적 분석

  1) 점근적 표기법을 사용한다.

    - 데이터의 개수 n->∞ 일때, 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법
        ex) 4n^2+5n+3 -> O(n^2), Θ(n^2)
  

  2) 유일한 분석법도 아니고 가장 좋은 분석법도 아니다. 다만 간단하며, 알고리즘의 실행환경에 비의존적이다.

• 상수 시간복잡도

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

n에 상관없이 상수 시간이 소요된다. 시간 복잡도 : O(1)

• 선형 시간복잡도

int sum(int data[],int n)
{
    int sum = 0;
    for (int i=0; i<n; i++)
    {
        // 이 알고리즘에서 가장 자주 실행되는 문장이며, 실행 횟수는 항상 n번이다.
        // 가장 자주 실행되는 문장의 실행 횟수가 n번이라면 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례한다.
        sum = sum + data[i]; 
    }
    return sum;
}

시간 복잡도 : O(n)

• 신형 시간복잡도(순차탐색)

int search(int n, int data[], int target)
{
    for(int i=0; i<n; i++)
    {
        if(data[i] == target)
            return i;
    }
    return -1;
}

이 경우 target과 n에 따라 시간복잡도가 달라진다. 최악의 경우는. data 배열의 마지막 인덱스가 target이 존재하는 경우이므로 최악의 경우 시간복잡도 : O(n)

• Quadratic (2차함수)

boolean is_distinct(int n, int data[])
{
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
        {
            if(data[i] == data[j])
                return false;
        }
    return true;
}

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