[Algorithm] 알고리즘의 분석

알고리즘의 분석 - 시간복잡도

 

 

알고리즘을 어떻게 평가 할 것인가? 어떠한 자료구조, 알고리즘이 적합한 것인가를 판단하기 위해 필요한 기준과 방법론

 

* 알고리즘의 분석, 좋은 알고리즘이란 무엇인가?

- 알고리즘의 자원(resource) 사용량을 분석 (보편적)

   - 자원이란 실행 시간, 메모리, 저장장치, 통신 등

- 여기서는 실행시간의 분석에 대해서 다룸

 

* 시간복잡도(time complexity)

- 실행시간은 실행환경에 따라 달라짐 (하드웨어, 운영체제, 언어, 컴파일러 등)
- 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 => 어떠한 환경에서 실행하더라도 동일

- 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 => n에 관한 함수로

- 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐

   ex) 배열에서 원하는 값을 찾는 경우 찾는 값이 배열 어디에 위치하는 지에 따라 달라질 수 있음

   - 최악의 경우 시간복잡도 (worst-case analysis)

      - 평균 시간복잡도가 구하기 더 어렵기 때문에 최악을 더 많이 사용

      - 데이터가 없는 경우, 모든 데이터를 다 비교하는 경우

   - 평균 시간복잡도 (average-case analysis)

 

* 점근적(Asymptotic) 분석

- 점근적 표기법을 사용

   - 데이터의 개수 n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법

   - Θ-표기, Ο-표기(빅오) 등을 사용

   (+) 빅오는  upper bound를 표현

   - 최고차항만 남기고 모두 버리는 것!
- 유일한 분석법도 아니고 가장 좋은 분석법도 아님

   - 다만 상대적으로 가장 간단하며 알고리즘의 실행환경에 비의존적임

   - 가장 광범위하게 사용됨

 

- 상수 시간복잡도

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

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

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

 

-  선형 시간복잡도

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

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

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

최악, 평균을 구분할 수 없음.

 

-  순차탐색

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

최악의 경우(데이터가 배열에 없는 경우) 시간복잡도는 𝑂(n)이다.

 

-  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;
  return true;
}

최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는 n(n-1)/2이다.

1 + 2 + 3 + ... + n-1
최악의 경우 시간복잡도는 𝑂(n^2)으로 나타낸다.

 

큼 -> 작음 순서

n^3(다항함수)과 2^n(지수함수) 는 굉장히 큰 차이가 있다.

 

---

 

이진검색과 정렬

 

* 이진검색

int binarySearch(int n, char *data[], char *target) {
	int begin = 0, end = n-1; 
    while(begin <= end) {
    	int middle = (begin + end)/2;
        int result = strcmp(data[middle], target); 
        if (result == 0) 
        	return middle; 
        else if (result < 0)
        	begin = middle+1;
        else 
        	end = middle-1;
     return -1; 
     }
}

한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어든다. 따라서 시간복잡도는 O(log2n)이다.

 

데이터가 연결리스트에 오름차순으로 정렬되어 있다면?

연결리스트에서는 가운데(middle) 데이터를 O(1)시간에 읽을 수 없음 => 따라서 이진검색을 할 수 없다.
순차검색의 시간복잡도는 O(n)이고 이진검색은 O(log2n)이다. 둘의 차이는 매우 크다.

 

* 버블정렬

void bubbleSort(int data[], int n) {
	for ( int i=n-1; i>0; i--) { 
		for ( int j=0; j<i; j++ ) {
        	if (data[j] > data[j+1]) { 
            	int tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp; 
			}
		} 
	}
}

시간복잡도: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n^2)

항상 O(n^2)

 

* 삽입정렬

void insertion_sort(int n, int data[])  {
    for ( int i=1; i<n; i++) {
        int tmp = data[i];
        int j = i-1;
        while (j>=0 && data[j]>tmp) {
            data[j+1] = data[j];
            j—;
        }
        data[j+1] = tmp;
    }
}

시간복잡도: 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n^2)

최선: O(n)

보통 삽입정렬이 버블정렬보다 빠르다

 

* 퀵소트(quicksort)
- 최악의 경우 O(n2), 하지만 평균 시간복잡도는 O(nlog2n)

* 합병정렬(merge sort), 힙 정렬(heap sort)

최악의 경우 O(nlog2n)의 시간복잡도를 가지는 정렬 알고리즘