[자료구조 - C언어] 자료구조 제19강: 시간복잡도와 점근적 분석(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 알고리즘의 분석

• 구조화, 모듈화가 얼마나 잘 되었는지에 따라 프로그램의 재사용성과 리팩토링이 달라질 수 있다.
  호환성 역시 마찬가지다.
  하지만 이러한 기준은 정량화 되어 있지 않기 때문에 이 장에서는 정량화된 기준으로 분석을 한다.
• 알고리즘의 자원(resource) 사용량을 분석
  • 실행 시간: 똑같은 시간 동안 얼마나 많은 일을 하는지
  • 메모리: 얼마나 많은 메모리를 사용해서 일을 하는지, 과거에는 중요했지만 기술의 발전으로 중요도가 낮아짐
  • 저장장치, 통신 등

 

2. 시간 복잡도(time complexity)

• 실행 시간은 실행환경(하드웨어, 운영체제, 언어, 컴파일러 등)에 따라 달라진다.
• 범용으로 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 한다.
  • (경우에 따라서는 real-time test 같은 실행 환경을 고정해두고 시간을 측정하는 상황도 있다.)
  • 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현된다. → n^2, 2n과 같이
    • 데이터의 크기가 같더라도 실제 데이터에 따라서 시간 복잡도가 달라진다.
      • 예) bubble sort와 같이 숫자를 비교하는 연산만 하지만
        → 입력 데이터가 몇 개인지에 따라 연산 횟수가 달라진다.
      • 시간 복잡도의 대푯값
        • 최악의 경우 시간 복잡도(worst-case analysis)
          • 이 알고리즘은 어떤 경우에도 이것보다 시간이 더 걸리지 않는 것을 보장한다.
        • 평균 시간 복잡도(average-case analysis)
          • 계산하기 어려워 주로 최악의 경우를 분석한다.
        • 최선의 경우는 대푯값으로 적절하지 않음

⇒ 알고리즘 안에 포함되어 있는 연산들의 실행 횟수를 최악의 경우 혹은 평균적인 경우에 대해 입력 데이터의 크기에 관한 함수로
     표현해 놓은 것을 시간 복잡도라고 한다.

 

3. 점근적 분석

• 점근적 표기법을 사용
  • 실제 정확한 함수 자체가 아니라 함수에서 데이터의 개수가 n→무한 일 때, 수행 시간이 증가하는 growth rate로 시간 복잡도를 표현
    • grwoth rate: 기울기에 상관하지 않고, n이 증가하면 함숫값은 비례해서 증가한다.
  • Θ-표기, O-표기 등을 사용
• 유일한 분석법도 아니고 가장 좋은 분석법도 아님, 다만 상대적으로 가장 간단하며 실행환경에 비의존적이라 가장 광범위하게 사용됨

3-1. 점근적 분석의 예: 상수 시간 복잡도

int sample(int data[], int n){
    int k= n/2;      //1번 실행
    return data[k];  //1번 실행
} => n에 관계 없이 상수 시간이 소요된다. 이 경우 알고리즘의 복잡도는 O(1)이다.

3-2. 점근적 분석의 예: 선형 시간 복잡도

int sum(int data[], int n){
    int sum = 0;
    for(int i=0; i<n; i++)
        sum = sum+data[i];    //가장 자주 실행되는 문장, 실행 횟수: n번
    return sum;
} => n에 선형적으로 비례하는 선형 시간 복잡도를 가진다. 시간 복잡도는 O(n)이다.

• 연산 횟수와 문장 실행 횟수를 동일선상에 두고 계산한다.
  • 가장 자주 실행되는 문장의 실행 횟수가 n번이라면
    • 모든 문장의 실행 횟수의 합은 n에 선형적으로 비례하며
      • 모든 연산들의 실행 횟수의 합도 역시 n에 선형적으로 비례한다. → 동일차수를 의미: 2n이나 4n이나 결국 O(n)이다.

3-3. 선형 시간 복잡도: 순차 탐색(sequential search)

int search(int n, int data[], int target){
    for(int i=0; i<n; i++){
        if(data[i] == target)    //가장 자주 실행되는 문장, 실행 횟수는 최악의 경우 n번
            return i;
    }
    return -1;
}  => 최선의 경우 O(1), 최악의 경우 O(n)의 시간 복잡도를 가진다.

3-4. Quadratic(2차)

bool is_distinct(int n, int x[]){
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++)
            if(x[i] == x[j];    //가장 자주 실행되는 문장, 최악의 경우 실행 횟수는 n(n-1)/2번
                return false;     //끝까지 같은 값이 없는 경우로, n-1 + n-2 + .. + 1의 실행횟수
    return true;
}  -> 최악의 경우 배열에 저장된 모든 원소 쌍을 비교하므로 비교 연산의 횟수는 n(n-1)/2
   => 최악의 경우 O(n^2)의 시간 복잡도를 가진다.

3-5. Logarithmic(로그)

for(int i=0; i<n; i*=2){
    //do something    //이 문장의 실행횟수는 루트 n번 
}  => O(log n)의 시간복잡도를 가진다.

 

4. 점근적 표기법

• 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법
• 최고차 항의 차수만 표시 → 가장 자주 실행되는 연산 혹은 문장의 실행 횟수를 고려하는 것으로 충분

4-1. Common Growth Rate

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/kg-bcK1ygIA