알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? (빅-오)

알고리즘 성능

알고리즘은 크게 시간과 공간을 통해 설명할 수 있다.

이 두 기준은 서로 상충하는 경우가 많다.

 

물론 더 빠르면서 메모리도 더 적게 사용하는 알고리즘이 있을 수 있지만,

메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서

메모리 사용량을 줄인 알고리즘들이 더 많이 존재한다.

ex) 동적 계획법의 경우에도 더 많은 메모리를 사용해 알고리즘의 수행 속도를 높이는 경우가 많다.

 

프로그램의 실행 시간을 단순히 측정하는 것에는 한계가 있다.

왜냐하면 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지

수많은 요소에 의해 바뀔 수 있기 때문이다.

 

이런 외적 요인을 전부 동일하게 하더라도 어떤 문자열 구현을 사용했는지,

함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라

프로그램의 최종 수행 시간은 크게 달라질 수 있다.

 

즉, 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못한다는 것이며,

알고리즘은 언제나 같은 속도로 동작하는 것이 아니며,

입력의 크기나 특성에 따라 수행 시간이 달라질 수 있다.

 

Big-O 기법을 이용한 시간복잡도 표시

O (N3)

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        for(int k=0;k<n;k++){...}

　

(N-M+1) * M → O(N × M)

for(int i = M-1; i<N; ++i){
    for(int j=0; j<M; ++j){ ... }
}

 

M-1 + (N-M+1) → O(N)

for(int i=0; i<M-1; ++i){...}
for(int i=M-1; i<N; ++i){...}

 

O(logN)

while(n)
    n/=2;

　

O(sqrt(N))

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

　

O(N logN)

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

　

O(N sqrt(N))

for(int i=0;i<n;i++)
    for(int j=0 ; j*j<=i ; j++);

 

피보나츠 수열 → O(2N)

int function(int n){
    if(n==0 || n==1)
        return 1;
    return function(n-1)+function(n-2);
}

　

nPn 으로 N개의 데이터를 나열하는 방법의 수 → O(N!)

void function(int x, vector<int> pick, vector<bool> picked){
    if(x==n){
        for(int i=0;i<pick.size();i++)
            printf("%d\n", pick[i]);
        return;
    }
    for(int i=0;i<n;i++){
        if(picked[i])
            continue;
        pick.push_back(i);
        picked[i]=true;
        function(x+1, pick, picked);
        pick.pop_back();
        picked[i]=false;
    }
    return;
}

 

Reference

- [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++)  

- [알고리즘] 코딩 테스트 문제 풀 때, 시간 복잡도 계산해보기  

- [C/C++] time(), clock()으로 실행시간 측정  

- 정렬 알고리즘 비교