자료구조와 알고리즘의 시간효율성

 

자료구조와 알고리즘을 다룰 때 중요한 것 두 가지가 공간의 효율성과 시간의 효율성이다. 

 

공간의 효율성은 메모리를 얼마나 차지하는지를 따지는 건데 해당 영역은 공부를 많이 안 했기 때문에 나중에 이야기하고, 지금은 시간의 효율성만 이야기 해보려한다. 또한 시간의 효율성도 많은 변수들이 있다. 지금은 시간의 효율성에서 내가 정확히 이야기할 수 있는 부분만 나눠두려고 한다. 

 

시간의 효율성은 속도, 시간복잡도 등등 여러가지 표현과 거의 동일하게 사용하는데, 알고리즘에서 효율성은 연산 단계이다. 

같은 결과를 얻기 위해서 가장 효율적인 방법을 채택할때 속도의 측면만 고려한다면, 연산 단계만 고려하면 된다. 

 

예를 들어 크기가 1~100까지가 저장되어 있는 배열에서 짝수만을 골라내려고 할 때 두 가지 예시 코드를 작성할 수 있다. 

 

아래 코드는 1~100까지의 자연수 배열을 모두 검사하여, 나머지가 0인 원소를 찾아내어 출력한다.

int[] ar = {1,2,3,4...100};

for(int i = 0; i < ar.length; i++) {
	if( ar[i]%2 == 0){
    	System.out.print(ar[i]+", ");
    }
}

 이렇게 할 때 컴퓨터는 내부적으로 ar이라는 배열의 인덱스 0부터 1씩 증가시키면서 검사하기 때문에 총 100단계의 연산이 진행된다. 

 

이를 조금 더 효율적으로 작성하자면 아래와 같다. 

int[] ar = {1,2,3,4...100};

for(int i = 1; i < ar.length; i+=2 ) {
    System.out.print(ar[i]+", ");
}

코드를 이렇게 작성한다면, 짝수연산임을 감안해서 2씩 더해가면서 진행하므로 총 50단계의 연산이 진행된다. 

 

이 두 가지의 경우를 조금 일반화하여 오름차순으로 정렬된 크기가 N인 자연수 배열이라고 생각한다면, 

앞의 로직의 경우 N단계 , 뒤의 로직의 경우 N/2단계가 수행된다. 

 

빅오 표기법으로 하면 O(N) , O(N/2)로 표현할 수 있다.