성능분석 방법(빅오 표기법)

모든 경우에 있어서 항상 우월한 성능을 보이는 자료구조와 알고리즘은 없다. 

그래서 자료구조와 알고리즘을 분석하고 평가 할 수 있어야 한다.

알고리즘의 성능 분석 평가 요소에는 2가지 복잡도가 있다.

복잡도란: 알고리즘의 성능을 객관적으로 평가하는 기준이다.

1. 시간복잡도(time complexity): 

- 알고리즘이 속도가 얼마나 빠른가? CPU가 얼마나 많은 일을 하는가?

- 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리킨다.

- 실행에 필요한 시간을 평가한것인데, 실제 시간은 여러 상황과 조건에 따라 달라질수 있다. 

그래서 객관적 판단 기준인 연산횟수로 시간 복잡도를 구한다.

1) 시간 복잡도의 평가 방법

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

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

- 이 함수에 데이터의 수를 입력하면 연산의 횟수가 계산된다.

- 데이터의 수가 적은 경우의 수행 속도는 큰 의미가 없다. 적으면 성능이 거의 만족스럽고, 어

떤 알고리즘이던 비슷 하게 만족스러운 결과를 내기 때문이다.

- 식을 구성하면 데이터의 수의 증가에 따른 연산 횟수의 변화하는 패턴을 알 수 있다. 

이것이 정말 중요하다!

 

이 그래프의 시간복잡도 함수

y = x   , T(n) = n 

x, n 축은 데이터의 수  

y, T(n) 축은 연산 횟수

2. 공간복잡도(space complexity): 

- 알고리즘이 얼마나 메모리를 적게 쓰는가? 

- 메모리 사용량에 대한 분석결과를 가리킨다.

- 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것이다.

3. 최적의 알고리즘이란?

메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라 할 수 있다. 그런데 일반적으로 알고리즘

을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다. 대게는 속도에 관심이 더 많고, 또 중

요한 요소로 판단되기 때문이다. 하지만 공간복잡도도 무시할 순 없다. 왜냐하면 메모리는 썻다가 

지웠다가 반복 접근을 하는데, 이때 메모리가 부족한 문제보다 메모리에 접근함에 따른 시간이 증

가 하기 때문에 공간복잡도도 따져봐야한다. 그리고 상대적인 우월성을 입증해야 하는경우 메모리

의 사용량도 함께 고려된다.

4. 최상, 최악, 평균의 경우

1) 최상의 경우(best case): 

  

시간복잡도의 최상의경우의 예를 하나 들어보겠다.

배열에서 내가 찾고자 하는 1의 값을 순차적으로 탐색하는 경우가 있다고 해보자. 그런데 배열 

인덱스 맨 앞에서 바로 원하는 값을 찾은 경우 이를 최상의 경우 라고 한다. 

이렇게 만족스러운 상황에서는 성능이 좋은 알고리즘이던 나쁜 알고리즘이던, 성능 평가의 주 

관심의 대상이 아니다. 최상의 경우 시간복잡도 함수 정의 T(n) = 1

          

2) 최악의 경우(worst case):

    위와 같은 경우에서 원하는 값을 배열의 끝에서 찾거나 대상이 저장되지 않은 경우.

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

    최악의 경우 시간복잡도 함수는 T(n) = n

    데이터의 수가 n개 있을때 연산횟수는 n이다.

3) 평균의 경우(Average Case):

평균적인 경우의 복잡도 계산은 어렵다.

왜냐하면 평균적인 경우의 연출이 어렵고,

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

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

반면 최악의 경우는 늘 일정하다.

4) 기준이 되는 경우

그래서 성능을 위한 시간복잡도를 평가할때는 거의 대부분

상황이 좋지 않은 최악의 경우를 기준으로 한다.

5. 빅오 표기법(Big O Notation)

복잡도에서 구한 함수인 T(n)에서 실제로 영향력을 끼치는 부분을 큰o로 감싸 가리켜 빅-오라 한다.

O는 order의 약자. n(데이터의수)의 변화에 따른 T(n)의 연산횟수의 변화 패턴을 판단하는것이 목적

이니 부차적인것은 무시할 수 있다. n이값을 커질때 나머지 부차적인것들을 버리고 기준을 마련해 

놓아서 표기해 놓은게 빅오 표기법이다. 부차적인것을 버리고 성능평가시 빅오만으로도 큰 결정적 

요소가 되며,기울기의 패턴을 구할 수 있다면 알고리즘 성능평가하는데 문제가없다.

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

6. 대표적인 빅오의 예

1) 상수형빅오 O(1)

o(1)은 데이터 수에 상관없이 연산횟수가 상수로 고정인 유형의 알고리즘을 뜻한다. 

연산의 횟수가 데이터 수에 상관없이 3회 진행되는 알고리즘일지라도 O(3)이 아니라 O(1) 이라 한다.

public class a02_OneSearch {
    
    static boolean OneSearch(int[] arr, int n) {
            
            return (arr[n] == 1) ? true:false;//중심이되는 연산
            //n에 관계없이 똑같은 시간이 소요된다. 
    }
 
    public static void main(String[] args) {
    
        int [] arr = {1,2,3,4,5,6,7,8,9,10};
 
        System.out.println(OneSearch(arr,0));//true
        System.out.println(OneSearch(arr,1));//false
    }
}

2) 선형 빅오 O(n)

O(n)은 입력한 데이터의 수와 연산횟수가 비례하여 증가하는 알고리즘을 의미한다. 그래프는 선의형태인 직선으로 표현된다.

예시로 순차탐색(앞에서 부터 뒤로 순차적으로 탐색해가는것) 알고리즘이 있다.

public class a03_LinearSearch {
    
    static int LSearch(int arr[], int length, int target){
        
        int i;
        
        for(i=0; i<length; i++) {//주변연산자들의 연산횟수는 중심이 되는 연산횟수에 의존적이다
        //위 연산자의 < 와 ++는   밑 if문의 연산자 ==이 true를 반환할때까지 수행되기 때문에 의존적이다.
            
            if(arr[i]==target)//중심이 되는 연산 //대상이 맞는지 순차적 확인 작업
                return i;    // 찾은 대상의 인덱스 값 반환
            
        }
        
        return -1;    // 찾지 못했음을 의미하는 값 반환
    }
    
    public static void main(String[] args) {
        
        int arr[]={3, 5, 2, 4, 9};
        int idx;
 
        idx=LSearch(arr, arr.length, 4);
        
        if(idx==-1)
            System.out.println("탐색 실패");
        else
            System.out.printf("타겟이 저장된 인덱스: %d \n", idx);
    }
}

위 순차탐색에서 데이터(n)의 입력은 배열의 크기인 length인데 이 크기가 커질수록 중심이 되는 연산

횟수가 비례하여 증가한다. 최악의 경우 대상이 맞는지 확인하는 연산 작업(arr[i]==target)이 배열의 크

기와 같다.

3) 로그형 빅오 O(log n)

O(log n)은 로그식 데이터가 늘어날때마다 연산횟수가 줄어들어 거의 수평이 되는 패턴을 보이는 알고리즘이다. 

이런 알고리즘은 성능이 아주 좋다 라고 할 수 있음. 로그의 밑이 얼마냐에 따라서 차이가 나긴 하지만 성능관점에서 매우 미미하기 때문에 대부분 생략한다.

ㅇ

예시로 이진탐색 알고리즘을 살펴보자.

이진탐색은 배열이 정렬되어 있어야 한다는 제약은 따르지만 탐색대상이 반으로 줄어버리는 장점을 가져 순차 탐

색보다 훨씬 좋은 성능을 보인다.

정렬되어 있는 배열에서 값 3을 찾아가보자.

   

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

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

2로 나눠서 얻은 4를 인덱스 값으로 구한다.

4번째 인덱스에 저장된 값이 3이 맞는지 확인후

맞지 않다면 저장된 값 9와 3의 대소를 비교해 대상의 범위를 줄여나감을 반복하자

 

이때 최악의 경우 연산횟수의 규칙을 찾아보자

처음 탐색 대상의 데이터수는 8개인데 이를 2로 나눈후 연산을 1회 시행한다

다시 4를 2로 나눈후 연산을 1회 시행하고

2를 2로 나눈후 연산을 1회 시행하면

데이터의 수가 1개 남는다 이때 마지막으로 한번더 실행하면 탐색대상이 없어지고 타겟을 찾지 못하게 된다.

데이터수 8 이 1이 되기까지 2로 나눈 횟수 총 3회 비교 연산 3회를 진행한다

그리고 데이터가 1개 남았을때 비교 연산 1회를 더 진행한다.

이것을 일반화 시키면

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

그리고 데이터가 1개 남았을때 비교 연산 1회를 더 진행한다.

T(n) = k+1 이라는 시간복잡도를 구할수 있다.

이제 k만 구하면 된다.

시간복잡도는 

 

을 최종적으로 구할 수 있다.

이 시간복잡도의 빅오는 

로그 밑과 상수를 생략하여

O(log n)이 된다.

참고로 선형 빅오와 로그형 빅오의 경우를 비교해보면

다음과 같이 로그형 빅오인 이진탐색의 예에서 연산횟수가 급격히 줄어들을 확인할 수 있다. 

4)  지수형 빅오 O(n^2)-quadratic time -n스퀘어라고도 부름

지수식은 처리해야할 데이터가 늘어날때마다 연산횟수(시간)가 기하급수적으로 증가하는 패턴을 보이는 알고리즘이다. 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다. 처음에는 조금씩 상승하다 나중에는 수직상승되는 그래프이다. 따라서 성능면에서는 좋지 못한 알고리즘이다.

예시로 중첩된 반복문이 있다 1차원 배열내에서 원소들중 2개의 원소의 합이 100이 넘는 경우를 탐색해보자 

최악의 경우 연산횟수가 배열의 사이즈 9(데이터수)의 제곱인 81회까지 연산을 하게 된다.

5) O(n^3) -cubic time

데이터의 수의 3제곱에 해당하는 연산횟수를 요구하는 알고리즘이다.

이 예제로는 삼중으로 중첩된 반복문이 있다. 앞서본 O(n^2)보다도 더욱 좋지 못한 성능을 가진 알고리즘이다.

7.기타