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

※ 알고리즘 분석

 - 알고리즘의 실행 시간 및 기타 자원의 사용량을 분석

 - 기타 자원으로는 메모리, 저장장치, 통신 등이 있다.

 - 알고리즘 분석에는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)를 이용한다. 

 - 주로 수행시간(시간 복잡도)을 분석한다.

※ 공간 복잡도

 - 알고리즘을 실행하여 종료할때까지 필요한 기억장치의 크기

 - 알고리즘과 무관한 부분 : 프로그램 코드를 저장하기 위한 공간, 프로그램을 수행하기 위해 시스템이 필요로 하는 공간

 - 알고리즘과 밀접한 부분 : 문제를 해결하기 위해 필요한 공간 ex)변수를 저장하기 위한 공간

예제) 공간 복잡도의 계산

public int fn_abc(int a, int b, int c){

    return (a+b+c)*a*b*c;

}

공간 복잡도 = 0

이유 : int a,b,c는 파라미터(전달되는 인자)로써 fn_abc에서 해결하고자 하는 문제와는 무관하다.

     

      --------------------------------------------------------------------------------------------------------------------------    

public int fn_sum(int a[], int n){

    int result =0;          

    for(int i=0; i<n ; i++){

        result += a[i];

    }

    

    return result;

}

    

공간 복잡도 = n+3

이유 : 사용되는 변수는 a[], n,result,i 이다. 위에와는 다르게 파라미터로 넘어온 값들이 바로 리턴이 된 형태가 아니라 

         이러한 변수들이 for문을 도는데 사용되고 있다. 

   그러므로 ( a[]의 n개의 원소를 저장할 공간 ) + ( 변수 n,i,result를 위한 공간 ) 이 필요하다.

     

      --------------------------------------------------------------------------------------------------------------------------    

public int fn_sum(int a[], int n){

    if(n == 0){

        return 0;

    }else{

        return (fn_sum(a[], n-1) + a[n]); 

    } 

}

   

공간 복잡도 = (n-1)*3

이유 : 여기서 사용되는 변수는 n과 a[]의 n번째 원소이다. 하지만 재귀함수이므로 순환을 위해 필요한 복귀 주소가

   필요하다.

         그래서 총 n, a[n], 복귀주소의 공간이 필요하고 재귀함수의 특성상 fn_sum의 depth도 필요하다.

         함수를 한번 콜할때마다 변수를 담을 공간이 3개씩 필요하므로 3+3+3+3+3+3+3.....이 된다. 

         즉 depth는 (n-1) 이고 총 3개의 변수를 담을 공간이 필요하므로 (n-1)*3이다. 

※ 시간복잡도

 - 실행시간이 아닌 알고리즘을 구성하는 명령어들이 몇 번이나 실행되었는지(연산의 실행 횟수)를 나타낸다.

 - 데이터의 크기가 같더라도 실제 데이터에 따라 시간복잡도가 달라질 수 있다.(Worst Case, Average Case....)

 - 특별한 언급이 없다면 복잡도는 시간복잡도를 나타낸다.

 - 일반적으로 빅오(Big-O) 표기법을 사용한다.

    

     

     1 : 일정한 실행시간을 갖음, 변수 선언등...

     log N : 주로 큰 크기의 문제를 일정한 크기를 갖는 작은 문제로 쪼개는 경우 발생 

                ex) 효율좋은 검색 알고리즘

     N : 입력 자료의 수에 따라 선형적인 실행 시간이 거릴는 경우

     N log N : 주로 큰 크기의 문제를 쪼개고(log N) 다시 하나로 모으는 경우 발생(N) 

                    ex) 효율좋은 정렬 알고리즘

     N^2 : 이중 루프

     N^3 : 삼중 루프

예제) 시간 복잡도의 계산 

 

public void ex1(int n){

    

    int count = 0;                     1

    for(int i = 0 ; i<n ; i++){        n+1

        count ++;                      n

    }    

}

시간복잡도 = O(n)

이유 : 위에서 시간 복잡도는 명령어의 실행 빈도수라 하였다. 예시에 빈도수는 빨간색으로 표시해 놨다. 

         이 빈도수를 모두 더하면 2n+2가 된다. 하지만 빅오 표기법은 n이 매우 큰 경우의 실행 시간인 점근적인 

   실행시간만을 따진다.

         만약 n이 무한대로 간다면 n이나 n+2나 별 차이가 없기 때문에 상수항은 무시하고 최고차항만을 남긴다.

         그렇기 때문에 위의 코드의 시간복잡도는 O(n)이 된다.

      --------------------------------------------------------------------------------------------------------------------------    

public void ex2(int n){

    

    int count = 0;                     1

    for(int i = 0 ; i<n ; i++){        n+1

        for(int j = 0 ; j<=i; j++){    (n*(n+1)/2) + 1

            count ++;                  (n*(n+1))/2

        }                      

    }    

}

시간복잡도 = O(n^2)

이유 : 위의 시간 실행 빈도수를 모두 더하면 n^2+n+3이 된다. 여기서 최고차항은 n의 제곱이므로 최고차항을 남기고 

   모두 지우면 시간복잡도는 O(n^2)이 된다.