[알고리즘] 복잡도

🛠 복잡도

프로그램의 실행속도는 프로그램이 동작되는 하드웨어나 컴파일러 등의 조건에 따라 달라진다.
알고리즘의 성능을 객관적으로, 정량적으로 평가하는 기준을 복잡도(Complexity)라고 한다.

시간복잡도 : 실행에 필요한 시간을 평가 = 얼마나 빠르냐
공간복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가 평가 = 얼마나 메모리 잡아먹냐?

요즘은 하드웨어의 비약적인 발전들로 인해 공간복잡도는 시간복잡도에 비해 약간 중요도가 떨어지는 것 같다. 물론 데스크톱이나 노트북이 아닌 가전제품같이 임베디드 프로그래밍을 할땐 다르겠지만 말이다.

시간복잡도의 대소관계는 아래와 같이 나타낼 수 있다.

1 -- $log N$ -- N -- $N log N$ -- $N^2$ -- $N^K$ -- $2^N$

오른쪽으로 갈수록 실행 시간이 길다고 생각하면 된다.
복잡도를 표시할때는 대문자 O를 써서 표현한다. 예를 들어 O(1), O(N)

아래 코드에서 시간복잡도를 한번 구해본다.

static int Search(int[] a, int n, int key) {
	int i = 0;
    	while(i < n) {
    		if(a[i]==key) 
        		return i;
        	i++;
    	}
   	return -1;
}

위 코드에서 int i = 1;, return i;, return -1; 은 메서드가 실행되는 동안 최대 한번만 수행이 된다. 이 경우 복잡도는 세개 모두 O(1) 이다.
반면 while(i<n) , if(a[i]==key), i++; 들은 최대 n번까지 실행이 될 수 있다. 즉 복잡도가 O(N)이다.

복잡도를 계산하는 방법은 책에서 다음과 같이 소개하고 있다.

O(f(n)) + O(g(n)) = O(max(f(n),g(n))) // max(a,b)는 두개 중 더 큰쪽을 나타냄

그렇다면 위 메서드에서 복잡도를 구해본다면
O(1) + O(N) + O(N) + O(1) + O(N) + O(1) 이 되는데 이는 그냥 O(N)이 된다.

전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.!