[자료구조] 복잡도(Complexity)

자료구조는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다.

 

복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

시간 복잡도(time complexity)

시간 복잡도란 '문제를 해결하는 데 걸리는 시간과 입력의 함수 관계'를 가리킨다.

어떤 알고리즘의 로직이 '얼마나 오래' 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다.

예를 들어, 입력 크기 n에 대한 알고리즘에 필요한 시간이 10n^2+n이라고 하면 빅오 표기법으로는 O(n^2)가 된다.

'가장 영향을 많이 끼치는 항'의 상수 인자를 빼고 나머지 항을 없애서 표현한 것이다.

다른 항들도 신경 쓰일 수 있지만 증가 속도를 고려한다면 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 때문에 이 항만 신경쓰면 된다는 이론이다. 

// 10n^2
for (int i=0;i<10;i++) {
	for (int j=0;j<n;j++) {
    	for (int k=0;k<n;k++) {
        	if (true) cout << k << '\n';
        }
    }
}

// n
for (int i=0;i<n;i++) {
	if (true) cout << i << '\n';
}

이와 같은 시간 복잡도는 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.

예를 들어, 어떤 알고리즘의 시간 복잡도가 O(n^2)이고 실제로 9초가 걸린다면, 코드를 시간 복잡도 O(n)의 알고리즘으로 개선한다면 3초가 걸린다. 이처럼 코드의 효율성에 대한 척도가 될 수 있고, 이 효율성을 더 좋게 만들어야 한다고 할 수 있는 척도가 된다.

 

 위 그림에서 O(1)과 O(n)을 비교해보면 입력 크기가 커질수록 차이가 많이 나는 것을 볼 수 있다. 당연히 그 O(n^2)도 훨씬 차이가 많이 난다. 

즉, O(n^2)보다는 O(n)을, O(n)보다는 O(1)을 지향해야 한다. 

O(2^n) > O(n^2) > O(n log n) > O(n) > O(log n) > O(1)

 

공간 복잡도(space complexity)

공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다. 

정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간이 추가적으로 계속 필요로 할 경우도 포함한다.

int a[1004];

예를 들어, 어떤 코드에서 이러한 정수형 배열을 선언했을 때 1004 * 4 바이트의 크기의 공간을 차지하게 되는 부분을 말하는 것이다. 

 

자료 구조에서의 시간 복잡도

자료구조를 사용할 때는 이러한 시간 복잡도를 잘 생각해야 한다.

다음은 자주 쓰는 자료 구조의 시간 복잡도를 나타낸 표이다. 보통 시간 복잡도를 생각할 때 평균과 최악의 시간 복잡도를 고려해서 쓴다.

 

자료 구조별 평균 시간 복잡도

자료 구조	접근	탐색	삽입	석재
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

자료 구조별 최악 시간 복잡도

자료 구조	접근	탐색	삽입	석재
배열	O(1)	O(n)	O(n)	O(n)
스택	O(n)	O(n)	O(1)	O(1)
큐	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)