[Data Structures][01-2] 알고리즘의 성능 분석 방법

본 글은 윤성우의 열혈 자료구조 책을 읽고, 강의를 수강하고 복습한 것을 기록한 글입니다.

강의 교안 또한 참고하여 작성하였습니다.

(강의 교안의 경우 오렌지 미디어에서 다운로드할 수 있습니다)

---

목차

- 시간 복잡도 & 공간 복잡도 

- 순차 탐색 알고리즘과 시간 복잡도

  - 최악의 경우와 최상의 경우

  - 순차 탐색 최악의 경우 시간 복잡도

  - 순차 탐색 평균적 경우 시간 복잡도

- 이진 탐색 알고리즘의 소개

  - 이진 탐색 알고리즘 최악의 경우 시간 복잡도

- 빅-오 표기법(Big-Oh Notation)

  - 단순하게 빅-오 구하기

  - 대표적인 빅-오

  - 순차 탐색 알고리즘 vs 이진 탐색 알고리즘

  - 빅-오에 대한 수학적 접근

 

---

시간 복잡도 & 공간 복잡도

알고리즘을 평가하는 두 가지 요소

- 시간 복잡도(time complexity) -> 얼마나 빠른가? (CPU - 80~90 %)

- 공간 복잡도(space complexity) -> 얼마나 메모리를 적게 쓰는가? (Memory - 20~10 %)

- 시간 복잡도를 더 중요시한다.

 

시간 복잡도의 평가 방법

- 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다.

- 데이터의 수에 대한 연산 횟수의 함수 T(n)을 구한다.

 

알고리즘의 수행 속도 비교 기준

 

 

 

- 데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다.

- 데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

 

---

순차 탐색 알고리즘과 시간 복잡도

 

// 순차 탐색 알고리즘 적용된 함수
int LSearch(int ar[], int len, int target)
{
    int i;
    for(i=0; i<len; i++)
    {
    	if(ar[i] == target)
            return i;	// 찾은 대상의 인덱스 값 반환
    }
    return -1;	// 찾지 못했음을 의미하는 값 반환
}

 

---

최악의 경우와 최상의 경우

순차 탐색 상황 하나: 운이 좋은 경우

- 배열의 맨 앞에서 대상을 찾는 경우

- 만족스러운 상황이므로 성능평가의 주 관심이 아니다!

- '최상의 경우(best case)'라 한다.

 

시간 복잡도와 공간 복잡도 각각에 대해서 최악의 경우와 최상의 경우를 구할 수 있다.

 

순차 탐색 상황 둘: 운이 좋지 않은 경우

- 배열의 끝에서 찾거나 대상이 저장되지 않은 경우

- 만족스럽지 못한 상황이므로 성능평가의 주 관심이다!

- '최악의 경우(worst case)'라 한다.

 

---

평균적인 경우(Average Case)

가장 현실적인 경우에 해당한다.

- 일반적으로 등장하는 상황에 대한 경우의 수이다.

- 최상의 경우와 달리 알고리즘 평가에 도움이 된다.

- 하지만 계산하기가 어렵다. 객관적 평가가 쉽지 않다.

 

평균적인 경우의 복잡도 계산이 어려운 이유

- '평균적인 경우'의 연출이 어렵다.

- '평균적인 경우'임을 증명하기 어렵다.

- '평균적인 경우'는 상황에 따라 달라진다.

 

---

순차 탐색 최악의 경우 시간 복잡도

"데이터의 수가 n개일 때,

                           최악의 경우에 해당하는 연산 횟수는(비교 연산의 횟수는) n이다."

 

T(n) = n           최악의 경우를 대상으로 정의한 함수 T(n)

 

---

순차 탐색 평균적 경우 시간 복잡도

가정1   탐색 대상이 배열에 존재하지 않을 확률 50%

가정2   배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률 동일!

 

탐색 대상이 존재하지 않는 경우의 연산횟수는 n

가정 2에 의해서 탐색 대상이 존재하는 경우의 연산 횟수는 n/2

 

가정 1과 2는 평균적인 경우라 할 수 있겠는가? 그렇다면 무엇이 평균적인 경우이겠는가?

 

 

평균적 경우를 구하기 어려울 뿐만 아니라 순차 탐색의 평균적 경우라고 가정한 가정의 근거를 증명하기 어렵다.

그렇기 때문에 최악의 경우를 구하고 나서 알고리즘 보조적 수단으로 활용된다.  

 

---

이진 탐색 알고리즘의 소개

이진 탐색 알고리즘의 첫 번째 시도:

1. 배열 인덱스의 시작과 끝은 각각 0과 8이다.

2. 0과 8을 합하여 그 결과를 2로 나눈다.

3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인!

순차 탐색보다 훨씬 좋은 성능을 보이지만, 배열이 정렬되어 있어야 한다는 제약이 따른다.

 

 

이진 탐색 알고리즘의 두 번째 시도:

1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다.

2. 대소 비교 결과는 arr[4] > 3이므로 탐색 범위를 인덱스 기준 0~3으로 제한!

3. 0과 3을 더하여 그 결과를 2로 나눈다. 이때 나머지는 버린다.

4. 2로 나눠서 얻은 결과가 1이니 arr[1]에 저장된 값이 3인지 확인한다.

탐색의 대상이 첫 번째 시도 이후 반으로 줄었다!

 

 

이진 탐색 알고리즘의 세 번째 시도:

1. arr[1]에 저장된 값 2와 탐색 대상인 3의 대소를 비교한다.

2. 대소 비교 결과 arr[1] < 3이므로 탐색의 범위를 인덱스 기준 2~3으로 제한!

3. 2와 3을 더하여 그 결과를 2로 나눈다. 이때 나머지를 버린다.

4. 2로 나눠서 얻은 결과가 2이니 arr[2]에 저장된 값이 3인지 확인한다.

탐색의 대상이 다시 반으로 줄었다!

 

이진 탐색의 매 과정마다 탐색의 대상을 반씩 줄여나가기 때문에 순차 탐색보다 비교적 좋은 성능을 보인다.

 

---

이진 탐색 알고리즘의 구현

 

이진 탐색의 기본 골격

while(first <= last)	// first <= last 가 반족의 조건임에 주의!
{
	// 이진 탐색 알고리즘의 진행
}

 

이진 탐색 알고리즘 예시

int BSearch(int ar[], int len, int target)
{
    int first = 0;	// 탐색 대상의 시작 인덱스 값
    int last = len-1;	// 탐색 대상의 마지막 인덱스 값
    int mid;
    
    while(first <= last)
    {
    	mid = (first+last) / 2;	// 탐색 대상의 중앙을 찾는다.
        if(target == ar[mid])	// 중앙에 저장된 것이 타겟이라면
        {
        	return mid;	// 탐색 완료!
        }
        else	// 타겟이 아니라면 탐색 대상을 반으로 줄인다.
        {
            if(target < ar[mid])
            	last = mid-1;	// 왜 -1을 하였을까?
            else
            	first = mid+1;	// 왜 +1을 하였을까?
        }
    }
    return -1;	// 찾지 못했을 때 반환되는 값 -1
}

 

위 코드에서 -1, +1을 추가한 이유는 아래와 같습니다.

 

-1 혹은 +1을 추가하지 않으면

first <= mid <=  last 가 항상 성립이 되어,

탐색  대상이 존재하지 않는 경우 first와 last의

역전 현상이 발생하지 않는다!

 

---

이진 탐색 알고리즘 최악의 경우 시간 복잡도

 

데이터의 수가 n개일 때, 최악의 경우에 발생하는 비교 연산의 횟수는?

 

 

 

=> 데이터의 수가 n개일 때 비교 연산의 횟수

 

- 처음에 데이터 수가 n개일 때의 탐색과정에서 1회의 비교연산 진행

- 데이터의 수를 반으로 줄여서 그 수가 n/2개일 때의 탐색과정에서 1회 비교연산 진행

- 데이터의 수를 반으로 줄여서 그 수가 n/4개일 때의 탐색과정에서 1회 비교연산 진행

- 데이터의 수를 반으로 줄여서 그 수가 n/8개일 때의 탐색과정에서 1회 비교연산 진행

 

.... n이 얼마인지 결정되지 않았으니

   이 사이에 도대체 몇 번의 비교 연산이 진행되는지 알 수가 없다!...

 

데이터 수를 반으로 줄여서 그 수가 1개일 때의 탐색과정에서 1회의 비교연산 진행

 

이러한 표현 방법으로는 객관적 성능 비교 불가!

 

 

 

=> 비교 연산의 횟수의 예

 

- 8이 1이 되기까지 2로 나눈 횟수 3회, 따라서 비교연산 3회 진행

- 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행

 

 

=> 비교 연산의 횟수의 일반화

 

- n이 1이 되기까지 2로 나눈 횟수 k회, 따라서 비교연산 k회 진행

- 데이터가 1개 남았을 때, 이때 마지막으로 비교연산 1회 진행

 

 

=> 비교 연산의 횟수의 1차 결론!

 

- 최악의 경우에 대한 시간 복잡도 함수 T(n)=k+1  이제 k만 구하면 된다!

 

 

 

 

그렇다면 +1이 아닌 +200 인 경우도 생략이 가능한가?

빅-오에 대한 이해를 통해서 이에 대한 답을 얻자!

 

---

빅-오 표기법(Big-Oh Notation)

T(n)에서 실제로 영향력을 끼치는 부분을 가리켜 빅-오(Big-Oh)라 한다.

 

 

=> n의 변화에  따른 T(n)의 변화  정도를 판단하는 것이 목적이니 +1은 무시할 수 있다.

 

 

=> 2n도 근사치 식의 구성에서 제외시킬 수 있음을 보인 결과!

     n이 증가함에 따라 2n+1이 차지하는 비율은 미미해진다.

 

---

단순하게 빅-오 구하기

=> 빅-오는?

- T(n)이 다항식으로 표현이 된 경우, 최고차 항의 차수가 빅-오가 된다.

 

=> 빅-오 결정의 예

 

 

=> 빅-오 결정의 일반화

 

 

---

대표적인 빅-오

 

 

---

순차 탐색 알고리즘 vs 이진 탐색 알고리즘

 

                        순차 탐색의 최악의 경우 시간 복잡도                                        순차 탐색의 빅-오

 

                        이진 탐색의 최악의 경우 시간 복잡도                                       이진 탐색의 빅-오

 

 

    최악의 경우에 진행이 되는 연산의 횟수

(보다시피 순차 탐색 연산 횟수가 기하급수적으로 늘어나는 것을 볼 수 있다)

 

 

---

빅-오에 대한 수학적 접근

=> 빅-오의 수학적 정의

=> 빅-오의 실질적인 의미

=> 빅-오 판별의 예

 

 

---

Reference

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9788996094067&orderClick=LEa&Kc= 

윤성우의 열혈 자료구조 - 교보문고

 

 

http://www.orentec.co.kr/teachlist/teach_main.php

====== 오렌지 미디어 ======

 

---