빅오 표기법(Big O)의 이해 - 시간 복잡도

알고리즘을 풀면서 시간 복잡도에 대한 개념은 자주 나온다.

 

O(n), O(log n), O(log n^2),...등등

 

실제로 문제 풀이에 있어서 큰 영향을 미치지 않는다고 생각했지만, 점차 문제가 어려워짐에 따라

 

문제는 맞았을지 몰라도, 효율성 테스트에서 낮은 점수를 맞곤 하였다.

 

알고리즘은 효율성의 싸움이기도 하니, 알고리즘 문제 풀 때, 최대한 효율적으로 짜기 위해 시간 복잡도를 나타내는 

 

빅오 표기법에 대해 이해해보려 한다.

 

 

 

1. O(1)

오원은 배열의 요소를 참조하는 알고리즘의 시간 복잡도를 나타낸다.

 

입력된 데이터의 크기와 상관 없이 항상 일정한 시간이 걸리는 알고리즘이기 때문이다.

O(1) 시간 복잡도 그래프

 

 

 

 

2. O(n)

오엔은 순차탐색 알고리즘의 시간 복잡도를 나타낸다.

 

F(int[] n) {
	(for i = 0 to n.length)
		print i
}

F라는 함수가 n을 매개변수로 받을 때, n의 크기가 늘어남에 따라 for문의 처리 속도가 늘어난다.

 

결국, data가 증가함에 따라 시간이 늘어나기 때문에 해당 그래프는 이렇게 된다.

O(n) 시간 복잡도 그래프

 

 

 

 

3. O(n^2)

오엔 스퀘어 또는 오엔 제곱 시간 복잡도는 2차원 배열의 시간 복잡도를 나타낸다.

F(int[] n) {
	for i = 0 to n.length
    		for j = 0 to n.length
        		print i + j;
}

i가 0 일때 j가 n의 크기만큼 돌고, 다 돌면 다시 i가 1이 되고, j가 0부터 n크기 만큼 도는 과정이 반복된다.

 

해당 시간 복잡도는 가로 n, 세로 n 크기의 정사각형을 그린다고 생각하면 더 편하다.

 

O(n^2) 시간 복잡도 그래프

처음엔 시간이 얼마 안 걸리지만, data가 증가함에 따라 많은 시간이 소요된다.

 

 

 

4. O(nm)

오엔엠은 오엔 스퀘어와 동일해 보이지만, 길이가 다른 직사각형을 그리는 것이므로,

 

시간 복잡도는 다르게 표현된다.

F(int[] n, int[] m) {
	for i = 0 to n.length
    		for j = 0 to m.length
        		print i + j;
}

O(nm) 시간 복잡도 그래프

 

 

 

 

 

5. O(n^3)

오엔 세제곱 시간복잡도는 3차원 배열이라 생각할 수 있다.

 

가로, 세로, 높이를 가지고 있는 큐빅를 떠올리면 더 편할 것이다.

F(int[] n) {
	for i = 0 to n.length
    		for j = 0 to n.length
            		for k = 0 to n.length
	        			print i + j + k;
}

O(n)은 직선이 되고, O(n^2)은 면적이 되고, O(n^3)은 n^2을 n만큼 더 반복하게 되는 것이니 큐빅이 된다.

O(n^3) 시간 복잡도 그래프

O(n^2)과 비슷한 양상을 띄지만, 높이 까지 계산하다 보니, 처리 시간이 더 오래 걸린다.

 

 

 

 

 

 

6. O(2^n)

오이엔제곱은 피보나치 수열 알고리즘에서 주로 사용되며, 재귀함수에서 나타나는 시간 복잡도라고 생각할 수 있다.

 

1, 1, 2, 3, 5, 8, 13, 21

 

위와 같이 두 숫자를 더해서 나 자신을 만들고, 다시 나 자신과 앞 숫자를 더해서 다음 수를 만드는 것이 피보나치 수열이다.

F(n, r) {
	if (n <= 0) return 0;
    else if (n == 1) return r[n] = 1;
    	
    // r[n]은 구해지는 수를 말한다.
    return r[n] = F(n - 1, r) + F(n - 2, r);
}

O(2^n) 시간 복잡도 그래프

O(2^n)의 시간복잡도는 O(n^2)과 O(n^3)보다 현저히 오래 걸리는 것을 볼 수 있다.

 

 

 

 

 

 

7. O(log n)

오로그엔은 이진 탐색 알고리즘의 시간 복잡도를 나타낸다.

 

오름 차순으로 정렬되어 있는 배열 중에서 key 값을 찾을 때, 절반씩 잘라 비교하는 알고리즘이다.

F(key, array, start, end) {
	if (start > end) return -1;
    	
        // 배열의 중간 인덱스 값을 찾는다
    	mid = (start + end) / 2;
    	
        // key와 중간 값이 같다면 리턴
    	if (array[mid] == key) return mid;
    	
        // key가 중간 값보다 작다면, key가 왼쪽에 있다는 뜻
        // end가 중간 인덱스-1
    	else if (array[mid] > key) return F(key, array, start, mid - 1);
    	
        // key가 중간 값보다 크다면, key가 오른쪽에 있다는 뜻
        // start가 중간 인덱스+1
    	else return F(key, array, mid + 1, end);
}

위 처럼, 절반을 잘라 비교 검색하기 때문에, 순차 검색인 O(n)보다 훨씬 빠르다.

O(logn) 시간 복잡도 그래프

 

 

 

 

마무리

지금까지, 총 7가지의 빅오 표기법과 그래프들을 알아봤다.

 

이외에도, 퀵정렬 알고리즘을 나타내는 O(nlogn), 브루트포스 알고리즘을 나타내는 O(n!) 등등이 있다.

 

저 정도만 알아도, 기본적인 개념은 자리 잡혔으므로 앞으로 문제 풀이하면서 궁금한 것이 생기면 더 검색해봐야 할 것 같다.

 

 

 

마지막으로, 중요한 한 가지만 짚고 넘어가겠다.

 

두 반복문을 따로 호출하는 함수를 보자.

F(int[] n) {
	for i = 0 to n.length
	print i;
        
    	for i = 0; to n.length
    	print i;
}

두 반복은 각각 O(n) 시간이 걸린다. 그럼 저 함수는 O(2n)이 걸린다고 말할 수 있을까?

 

정답은 O(n)이 걸린다.

 

왜 그럴까? 시간 복잡도를 쉽게 말하자면, 입력이 n일 때 연산 횟수를 말한다.

 

그 횟수가 알고리즘의 속도를 나타내기 때문이다.

 

여기서, 중요한 것은 "빅오 표기법 앞에 붙는 상수는 무시한다." 이다.

 

왜냐하면, 빅오 표기법은 알고리즘의 Running Time을 재기 위해 만든 것이 아니라,

 

데이터 증가에 따른 처리 시간의 증가율을 예측하기 위해 만든 것이기 때문이다.

 

"n이 증가함에 따라" 가 더 중요한데, 고정된 상수는 의미가 없다는 것이다.