[Data Structure] 시간 복잡도, 공간 복잡도

* 시간 복잡도 

알고리즘의 수행시간을 분석한 결과를 말한다. 일반적으로 빅오 표기법(Big-O Notation)을 사용해 나타낸다.

 

1. Big-O

알고리즘의 성능을 수학적으로 표현해주는 표기법. 이를 통해 알고리즘의 시간 복잡도, 공간 복잡도를 표현할 수 있다. Big-O는  알고리즘의 실제 러닝타임을 표기하기보다는 알고리즘의 성능을 예측하는 데 사용된다. 

 

 

2. 상수(Constants)

위에서 언급했듯, Big-O의 용도는 실제 알고리즘 러닝타임이 아니라, 성능 예측이기 때문에 빅오 표기시 상수는 중요하게 고려하지 않아 제거한다. 

 

 

3. 표기

- O(1) : Constant Time

입력 데이터의 크기와 상관없이 언제나 일정 시간이 걸리는 경우다. 예를 들어, 연결 리스트의 맨 앞에 노드를 추가하는 작업의 경우 새 노드를 기존 연결리스트의 헤드와 붙여주기만 하면 된다. 이 경우, 연결리스트의 길고 짧음음 해당 작업시간에 영향을 주지 않는다. 이 때의 시간 복잡도를 O(1) 으로 표기한다.

 

- O(log n)

입력 데이터의 크기가 늘어나도 처리속도는 상대적으로 서서히 늘어난다. 대표적 알고리즘이 이진 검색(Binary Search)이다. 정렬된 배열에서 이진검색으로 특정 키를 찾고자 하면 먼저 가운데값을 찾아 키와 비교한다. 키가 가운뎃값 보다 작으면 가운뎃값의 왼쪽을, 크면 오른쪽을 확인한다. 이를 반복하여 원하는 키를 찾는다. 이진검색의 특징은 한 번 처리할 때마다 검색해야 할 데이터의 양이 절반으로 줄어든다는 점이다. 이를 O(long n)으로 표기한다.

그림에서 의 키는 6이고, 배열의 가운뎃값은 5이다. 6은 5보다 크므로, 가운데값 5의 좌측은 고려할 필요 없이 우측만 확인하면 된다. 우측의 가운뎃값은 7이고, 6은 7보다 작으므로 7의 좌측만을 검색한다. 7의 좌측에는 원하는 값인 6이 있으므로 이를 찾아주면 된다.

 

 

-  O(n) : Linear Time

입력 데이터의 크기와 정비례해서 시간이 늘어나는 경우다. 예를 들어, 연결 리스트에서 특정 노드를 찾는(search) 작업을 진행할 때, 헤드부터 차례로 노드를 찾아가야 한다. 따라서 연결리스트의 길이가 길 수록 사용되는 시간도 길어진다. 이 때의 시간 복잡도를 O(n)으로 표기한다.

 

 

 

- O(n²) : Quadratic Time

 

데이터가 늘 때마다 걸리는 시간이 데이터의 제곱으로 늘어나는 경우다. 처리해야하는 데이터가 늘어날 수록 소요시간은 수직상승한다. 예를 들어 이중루프의 경우, 배열의 길이의 제곱만큼의 시간이 소요된다. 

//이중루프
let arr = [1,2,3,4,5]
for(let i = 0; i < arr.length; i++){
	for(let k = 0; k < arr[i].length; k++){
		console.log(arr[i][k]);	
	}
}

//배열의 길이는 5이지만, 연산은 25(5*5) 번 시행됨.

 

 

* 공간 복잡도

시간 복잡도가 알고리즘의 수행시간을 측정한다면, 공간 복잡도는 알고리즘의 메모리 사용량에 대한 분석결과를 나타낸다. 시간 복잡도에 비해 사용도가 적은 편이다. 하드웨어(메모리)의 발전 속도가 빨라, 메모리 사용에 대한 부담이 상대적으로 줄어들었기 때문이다. 

* Reference : 엔지니어대한민국 (https://www.youtube.com/watch?v=6Iq5iMCVsXA), 견우와직녀(https://ledgku.tistory.com/33)