Big-O Notation, (시간,공간 복잡도)

코딩을 하다보면 자꾸 보이고 들리는 용어가 있다. 바로 시간 복잡도다.

대충 컴퓨터가 계산하는데 얼마나 걸리냐 정도로만 인식했지 제대로 알아본적이 없기 때문에

이번 기회에 제대로 알아보도록 하겠다 !!

 

Big-O 표기법이란?

알고리즘이 얼마나 효율적인지 따지는 지표이다.

내가 짠 코드의 반복문, 조건문이 몇개인가 또는 산술, 비교, 대입연산자에 따라 얼마나 걸리는지에 대해 "시간" 개념으로 얼마나 걸리는지에 대해 나타내는 표기법이다.

 

시간 복잡도란?

그럼 위에 표기법인 Big-o 표기법으로 계산을 하는데 몇 가지 규칙이 있다.

그럼 모든 코드의 반복문이나 연산자를 모두 봐야할까?

아니다, 코드의 핵심적인 부분의 입력 값 (N)과 그 N으로 부터 어떤 관계가 있는지를 파악하는게 제일 중요하다.
또 실제로 작동하는데 걸리는 시간이 우리가 예측한 시간과 다를 수 있다, Big-O는 아주 단순하게 얼마나 증가하는지에 대한 비율을 나타내는 개념이다. 그리고 알고리즘의 효율성을 따지기 위해선 데이터의 입력 값이 작은 경우는 가정하지 않고 데이터의 입력 값이 충분히 커야 효율성에 대한 의미가 생긴다.

1. 상수항은 무시한다.  예를들면 N²+1 일 때 입력 값 N이 100이라면 10,000 + 1 인데 여기서 1은 딱히 무시해도 상관 없다는 이야기다.  숫자가 커질 수록 상수항은 점점 의미가 없어진다. (100도 아주아주 낮게 잡은 것이다.)
2. 마찬가지로 계산에 딱히 의미가 없는 숫자는 무시한다. N²+N 일 때 N이 커지면 커질 수록 제곱 값을 따라올 수 없게되므로 무시한다.

아주 다양한 계산과 순서가 있지만 감을 잡고 넘어가는 기초만 보자면

O(1) < O(log n) < O(n) < O(n log n) < O(N²) < O(2ⁿ) < O(n!) < O(nⁿ) 정도이다.

*주의 : 항상 변수가 하나라는 법은 없다. 코드에서 사용된 변수와 핵심적인 부분에 따라 계산법은 아주 복잡해진다.

 

그럼 간단한 예제로 느낌을 잡아보자

for(int i =0; i<n; i++){
	sum = sum + n;
}

for문만 보면 되기에 변수 선언은 뺏습니다.

for문의 안을 보면 대입연산 1개와 덧셈 연산 1개가 있습니다. 그리고 그걸 N번 만큼 반복하니 총 2N이 되지만 위에 규칙에서 상수항은 무시한다 했으니 O(N) 이 됩니다.

 

int multiplication(int n){
	return n * n;
}

위 메소드 안을 보면 곱셈 연산 1개만 있으므로 O(1) 이 됩니다.

 

그리고 2중 for문을 사용한 예제를 보면

for(int i = 0; i<n; i++){
	for(int j = 0; j<n; j++){
    	sum = sum + 1;
    }
}

안쪽 for문에는 대입연산 1개, 덧셈연산 1개가 있고 그걸 N번 반복하며 또 이걸 N번 반복합니다. 이것을 Big-O로 나타내면

O(2N²) 이지만 상수항은 무시해도 되니까 O(N²) 이 됩니다.

 

공간 복잡도란?

위에 시간복잡도가 반복문을 기준으로 "시간"개념에 집중했다면

공간 복잡도는 말 그대로 공간, 즉 배열같은 "공간"개념으로 보는 느낌이다. (시간 복잡도보다는 중요도가 조금 떨어짐)

 

int[] arrays = new int[n];

크기가 N인 배열을 만들었을 때 공간 복잡도는 O(N)이 된다.

 

int[][] doubleArrays = new int[n][n];

크기가 N인 2차원 배열을 만들면 공간 복잡도는 O(N * N) = O(N²) 이다.

 

 

 

 

 

 

 

 

 

오늘은 시간,공간 복잡도에 대해 알아봤는데 사실 아직까지 쓸 곳은 백준과 코딩테스트 같은 문제풀이 할 때 주어진 시간을 통과하기위해

사용하는 용도로만 느낌이 온다.

그래도 하나 배웠으니 언젠가 나중에 필요한 날이 더 생기지 않을까?