[ 자바 알고리즘/자료구조] - 시간복잡도 && 공간복잡도

복잡도

- 알고리즘의 성능을 객관적으로 평가하는 기준

 

복잡도 종류

1) 시간복잡도 : 실행에 필요한 시간이 얼마인지?

2) 공간복잡도 : 기억 영역과 파일 공간이 얼마나 필요한지?

 

method{
	int i = 0;
    while(i<num){
    	if(arr[i] == key){
        	return i;				//성공
        }
        i++;
    }
    return -1;						//실패
}

- int i = 0 -> 변수 i에  0을 대입하는 것은 한번이후 없으므로 O(1)

- return의 경우도 한번만 실행하므로 O(1)

- while의 조건과 if문, i++의 경우 평균횟수 n/2 -> n에 비례하는 경우의 복잡도를 O(n)으로 표기

 

n이 커지면 O(n)에 필요한 계산 시간은 n에 비례하여 점점 길어진다.

O(1)의 경우 계산 시간은 변하지 않는다.

 

O(f(n)) 과 O(g(n))의 복잡도 계산

- O(f(n)) + O(g(n)) = 0(max(f(n) , g(n))

- 2개 이상의 복잡도로 구성된 알고리즘의 전체 복잡도는 차원이 더 높은 쪽의 복잡도를 우선시한다.

- 선형 검색의 경우  -> 0(1) + 0(n) + 0(n) + 0(1) + 0(n) + 0(1) = 0(max(1,n,n,1,n,1)) = o(n) 이다.

 

이진탐색의 시간 복잡도를 알아보자

public class 이진탐색시간복잡도 {
	public static int binSearch(int[] arr, int n, int key) {
		int start = 0;  						//O(1)
		int end = n - 1; 						//O(1)
		
		do {
			int center = (start + end) / 2; 	// O(log n)
			if(arr[center] == key) { 			// O(log n)
				return center;			 		// O(1)
			}else if(arr[center] < key) {		// O(log n)
				start = center + 1;				// O(log n)
			}else {
				end = center - 1;				// O(log n)
			}
		}while(start <= end);
		return -1;								// O(1)
	}
	
	public static void main(String[] args) {
		int arr[] = {1,3,5,7,9,11};
		int key = 5;
		System.out.println(binSearch(arr,arr.length,key));
		
	}
}

 

복잡도 순서

1 < logN < N < n logN < n*2 < n^3 < n^n < 2^n