시간 복잡도

만약 당신이 IT 회사 면접자 신분으로 면접에 들어갔다. 

면접관 중 한명이 당신에게 묻는다. 

"대용량 트래픽을 처리해본 경험이 있으신가요?"

있다면, 처리해본 경험을 말해주면 되겠다.

하지만, 신입 개발자라면 대용량이 아니라 1000건의 트래픽도 경험해본적이 없을 것이다. 

하지만, 작은 데이터도 효율적으로 쓸 수 있는 방법은 없는 지 고민해봤더라면

경험은 없지만 어떻게 하면 대용량을 처리할 수 있는 지에 대한 방법론은 알 것이다. 

그것이 우리가 시간 복잡도에 대해 알아야 하고, 엔지니어라면 설령 양의 정수 A 와 B의 합을 구할 때도,

더 효율적인 방법은 없는가? 이것이 최선인가? 그 "효율"에 대해 고민해야 된다 생각한다. 

그러기 위해서 이제부터라도 꼭 시간 복잡도에 대해 공부를 해보자..

 

시간 복잡도는 그 종류가 빅오, 빅세타, 빅오메가 가 존재한다. 

순서대로 최악, 평균, 최선이라고 가정할 떄, 우리는 최악의 경우만 생각해 피한다면, 저절로 평균, 최선에 들어가지 않겠는가?

따라서 우리는 최악만 피하자 느낌으로 이해하면 편하겠다. 

 

그렇다면 우리가 최악을 피해야 되는 이유는 무엇일까?

특정 컴퓨터에서 계산기를 열었다고 가정해보자. 1 + 1 연산을 컴퓨터가 하는 데 1분...극단적으로 무한대 가까운 시간이 걸린다고 하자. 그럼 차라리 내가 풀고 말지 하는 생각이 드는 게 당연하다. 이처럼 사용자의 서비스 만족감을 높일 수도 있다. 

또한, 비용적인 측면에서 얼마나 알고리즘을 효율적으로 짜느냐에 따라 금액은 천차만별이 될 것이다. 매우 극단적으로 적절한 알고리즘을 사용하면 30만원 노트북으로 풀릴 걸, 슈퍼컴퓨터 6대를 사용해야 푸는 알고리즘과 자료구조를 선택했다 생각해보자. 회사 입장에선 시간 == 돈 이다.

 

크게 위의 이유로 우리는 최악을 피해야 하고, 최악을 피하기 위해 적절한 자료구조와 알고리즘을 사용하여 최적화를 해야 하는 것이다. 그 출발점이 시간 복잡도에 대해서 이해하는 것이라 생각한다. 

 

그럼 우린 어떻게 시간 복잡도를 계산할 수 있을까?

 

병합 정렬을 예로 들어보겠다.

 

우선, 간략하게 병합 정렬 ( merge sort )에 대해 설명하고 해당 예시의 시간 복잡도를 구해보자. 

 병합 정렬이란, 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다. 

https://studyiwthme.tistory.com/124 <- 자세한 건 클릭 (아마 읽으시면서 공부할 내용이 더 풍부해지실 겁니다.) 다 이해하고 넘어오셔도 좋고 아니셔도 이해 가능하게 작성하겠습니다.)

 

병합 정렬은 배열을 계속해서 반으로 나누는 과정이 있다. 

배열의 크기가 n 이라고 했을 때, 이걸 1개로 줄이는 과정은 

 

• 첫 번째 단계: 배열 크기 n을 절반으로 나누면 배열의 크기가 n/2​인 두 개의 배열로 나뉩니다.
• 두 번째 단계: 각각의 배열을 다시 절반으로 나눕니다. 이때 배열의 크기는 n/4​가 됩니다.
• 세 번째 단계: 다시 나누면 n/8​로 줄어듭니다.
• ...
• 마지막 단계에서는 배열의 크기가 1이 될 때까지 나누게 됩니다.

 

따라서

1) n 

2) n/2

3) n/4

4) ....

5) 1

(k를 횟수라고 한다면) 

따라서 배열을 반으로 나눌 때, 시간복잡도가 O(logN) 이 되는 이유이다. 

 

더 쉬운 예제를 봐보자. 

 

for i in range(10):
	print(i)

for 문에서 i 가 0부터 n-1 번까지 n 번 반복된다.

즉, 이 루프에서 n번 반복되므로 반복문의 시간 복잡도는 O(n) 이 된다. 

그러면 print(i) 는 폼이냐?? 대게 print(i)는 상수 시간안에 처리되며 O(1)의 시간복잡도를 갖는다. 

n 이 100 아니 1000000000000이라고 하자 거기에 1이 추가된다고 해도 유의미한 차이를 만들진 않는다. 따라서 빅오표기법에서는 고려를 하지 않는 것이다. 

 

위 같은 방식으로 시간 복잡도를 계산하면 좋다 

 

일반적으로 시간 복잡도가 N log(N) 이 넘어가면 쓸 수 없는 알고리즘 이라고 우선,,, 생각하면 편하다.