자료구조/알고리즘 시간복잡도

좋은 프로그램 알고리즘이란

- 신뢰성, 처리 효율, 범용성, 확장성, 이식성, 가독성 등이 높으면 좋은 알고리즘이라고 한다.

 

시간 복잡도는 입력되는 데이터의 증가에 따른 성능의 변화를 예측하는 것이다.

- Big O 표기법으로 표현한다.( O(n) ) : n 개의 데이터에 증가하는 변화율을 표현한다.

 

예시로 보면,

int func1(int[] n) {
	if(n.length < 3)
    	return 0;
        
    int a = n[0];
    a += n[1];
    a += n[2];
    
    return a;
}

이 예시에서 배열 n의 크기가 어느 정도이든 매번 똑같은 횟수로 기능을 처리하기 때문에 시간복잡도를 O(1)이라고 표현한다.(일정하다)

 

다음으로,

int sum(int[] n){
	int s = 0;
    
    for(int i : n){
    	s += i;
    }
    
    return s;
}

이 코드에서는 배열의 크기가 증가할 수 록 처리하는 횟수도 동일하게 증가하기 때문에 시간복잡도를 O(n)으로 표현한다.

(n에 정비례해서증가)

 

void bobbleSort(int[] n){
	for(int i=0; i<n.length; i++){
    	for(int j=0; j<n.length; j++){
        	if(n[i]<n[j]){
        		int temp = n[j];
            	n[j] = n[i];
            	n[i] = temp;
           	}
        }
    }
}

이 예시에선, n의 증가에 제곱으로 처리횟수가 많아지기 때문에 시간복잡도를 O(n^2)으로 표현한다.

(예로들면 n이 2일 경우에 첫번째 for문이 2번 돌고, 두번째 for문이 2번돌아 총 4번 처리된다.)

 

다음으로,

int sum(int[] n){
	int sum = 0;
    int max = n.length;
    while (max > 0){
    	sim += n[max - 1];
        max /= 2;
    }
    return sum;
 }

이 예시에선 n이 증가할수록 취급하는 데이터의 범위(max)가 절반씩 줄어들기 때문에 시간복잡도를 O(logn)으로 표현한다.