시간 복잡도 (Time complexity)

시간 복잡도

---

시간복잡도는 문제를 해결하기 위한 연산 횟수를 말하고 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다.

시간 복잡도의 표기법은 아래와 같이 3가지 유형이 있습니다.

• 최상의 경우 : 빅-오메가 표기법 (Big-Ω Notation) : 최선일 때
• 평균의 경우 : 빅-세타 표기법 (Big-θ Notation) : 보통일 때
• 최악의 경우 : 빅-오 표기법 (Big-O Notation) : 최악일 때

1 ~ 10의 숫자가 무작위로 섞여있을 때 임의의 값을 하나 찾는 프로그램이 있다고 할 때 각 표기법의 시간 복잡도는 아래와 같습니다.

• 빅-오메가 표기법 (Big-Ω Notation) : 1
• 빅-세타 표기법 (Big-θ Notation) : 2 / N
• 빅-오 표기법 (Big-O Notation) : N

시간 복잡도는 빅-오 표기법 (Big-O Notation)을 기준으로 수행시간을 계산하는 것이 좋습니다. 코드를 테스트 할 때 1개만의 테스트 케이스를 이용하지 않고 다양한 테스트 케이스를 사용하기 때문에 최악을 염두에 두어야 하기 때문입니다.

 

 

 

시간 복잡도 종류

---

출처 : https://www.bigocheatsheet.com/

 

O(1)

입력 크기 n과 상관없이 일정합니다.

int exam(int n){
	int a = n;
    return a;
}

입력의 영향을 받지 않으며 다른 연산이 필요없이 바로 수행되는 경우입니다.

 

O(logN)

입력 크기 n이 커질 수록 logN에 비례하여 증가합니다.

int binarySearch(int key, int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1;
}

연산이 진행 될수록 연산 횟수가 2로 나누어지는 경우입니다.

 

O(n)

입력 크기 n이 커질 수록 n에 비례하여 증가합니다.

for(int i = 0; i < n; i++){
	System.out.println(i);
}

반복문을 통해 연산이 n번 수행되는 경우입니다.

 

O(n²)

입력 크기 n이 커질 수록 n²에 비례하여 증가합니다.

for(int i = 0; i < n; i++){
	for(int j = 0; j < n; j++){
		System.out.println(i + " " + j);
	}
}

2중 반복문을 통해 연산이 n*n번 진행 될 경우입니다.

 

O(2ⁿ)

입력 크기 n이 커질 수록 2ⁿ에 비례하여 증가합니다.

int fibonacci(int n){
	if(n <= 1) return n;
	return fibonacci(n-1) + fibonacci(n-2);
}

피보나치 수열을 예로 들 수 있으며 연산이 2ⁿ번 수행되는 경우입니다.