본문 바로가기

플밍 is 뭔들/알고리즘

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

※ 알고리즘 분석
 - 알고리즘의 실행 시간 및 기타 자원의 사용량을 분석
 - 기타 자원으로는 메모리, 저장장치, 통신 등이 있다.
 - 알고리즘 분석에는 시간 복잡도(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)이 된다.