[알고리즘] 시간복잡도 (Time Complexity) 개념 정리

시간 복잡도

문제를 해결하기 위해 알고리즘의 로직을 코드로 구현할 때 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미한다.

 

 

시간 복잡도 표기법

• Big - O (빅 - 오)
• Big - Ω (빅 - 오메가)
• Big - θ (빅 - 세타)

위 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 이 중 Big - O 표기법이 가장 자주 사용된다. Big - O 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. 

 

O(1)

Constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

입력값의 크기와 상관없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.

public int algorithm(int[] arr, int index) {
  return arr[index];
}

int[] arr = new int[]{1,2,3,4,5};
int index = 1;
int results = algorithm(arr, index);
System.out.println(results); 

/* 출력
2
*/

이 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다. arr의 길이가 아무리 커져도 해당 index에 접근해 값을 반환할 수 있다.

 

O(log n)

logarithmic complexity라고 부르며 O(1)다음으로 빠른 시간 복잡도를 가진다. 이진 탐색 트리(Binary Search Tree)가 그 예이다. up & down을 예시로 들면 매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 O(log n)의 시간 복잡도를 가진 알고리즘이다.

 

O(n)

linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

입력값이 1일 때 1초의 시간이 걸리고, 입력값을 10배로 증가시켰을 때 10초가 걸리는 알고리즘은 O(n)의 시간 복잡도를 가진다고 말할 수 있다.

public void algorithm1(int n) {
	for(int i = 0; i < n; i++) {
	// do something for 1 second
	}
}

public void algorithm2(int n) {
	for(int i = 0; i < n * 2; i++) {
	// do something for 1 second
	}
}

algorithm1 함수에선 입력값(n)이 1 증가할 때마다 코드 실행  시간이 1초씩 증가한다. 입력값이 증가하면 같은 비율로 시간이 증가하고 있다. algorithm2 함수에선 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가한다. 그러면 O(2n)이라고 생각할 수 있지만 Big - O 표기법으로는 O(n)으로 표시한다.5배 10배로 증가하더라도 O(n) 으로 표시한다.

 

O(n^2)

quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

public void algorithm1(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			// do something for 1 second
		}
	}
}

public void algorithm2(int n) {
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < n; k++) {
				// do something for 1 second
			}
		}
	}
}

n^3과 n^5 모두 O(n^2)로 표기한다.

 

O(2^n)

exponential complexity라고 부르며 Big - O 표기법 중 가장 느린 시간 복잡도를 가진다.

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

재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘이다.