시간 복잡도는 왜 따져봐야 할까?

1.

O(N^2), O(N), O(logN)...

 

자료구조나 알고리즘 시간에 많이 보던 수식입니다.

머릿속에는 이런 형태의 공식으로 박혀있죠.

 

"x 알고리즘 = 복잡도 y"

 

저도 꽤 오랫동안 그랬던 것 같습니다.

하지만 현업에서도 이걸 잘 따져봐야 하는 일들이 가끔 생깁니다.

 

예를 들어봅시다.

당신이 만든 프로그램이 2중 for 문으로 구성되어있다고 합시다.

복잡도가 O(N^2) 라고 해보죠.

 

시간이 너무 오래 걸려서 개선을 하고 싶습니다.

당신은 N을 약 N-3 정도로 줄여서 약간 개선시켜, 다행히 사용 가능한 정도는 되었습니다. 

이건 잘 개선되었다고 말할 수 있을까요?

아마 높은 확률로 머지않아 문제가 생길 겁니다. 

 

그런데 새로운 방법을 생각해서 복잡도를 O(N*logN) 정도로 개선을 했다고 합시다.

이건 잘 개선된 것일까요?

 

네 저는 그렇게 생각합니다.

 

당장 숫자를 대입해봐도 확 차이가 날 겁니다. N=1,000 이라면,

 

개선전) 1,000 * 1,000 = 1,000,000 (100만)

개선1) 997 * 997 = 994,009 (약 99만)

개선2) 1,000 * 10 = 10,000 (1만)

 

이렇게 됩니다.

 

그래서 하고 싶은 말은 복잡도 자체를 줄여야 의미 있는 개선이 된다는 것입니다.

복잡도를 따져보는 일은 개선이 얼마큼 되었는지 측정하는데 필요하다는 이야기도 됩니다.

이렇게 단계마다 의미가 있기에 시간 복잡도를 그렇게 나눠놓은 것은 아닐까? 생각해봅니다.

 

2.

복잡도를 줄일 수 있는 지식을 몇 개 알고 있으면 좋습니다.

예를 들어, 정렬된 데이터가 있고 거기서 무언가를 찾아야 한다면 이진 탐색(binary search)을 적용할 수 있겠죠.

비슷한 알고리즘으로 하한과 상한을 찾는 lower_bound, upper_bound 도 적용해볼 수 있을 겁니다.

 

3.

해묵은 논쟁 중에 하나가 현업에서 알고리즘이 중요하냐, 안 중요하냐입니다.

보통 알고리즘 테크닉을 가지고 이야기하는 것 같은데, 그것은 논의의 본질이 아니라고 생각합니다.

중요한 것은 테크닉이 아니라, 문제에 부딪쳤을 때 복잡도를 따져보고 개선시켜갈 수 있는 능력이 있는가? 입니다.

그러니, 알고리즘을 달달 외우는 것이 아니라 원리를 기반으로 체화하고 있는 사람은 당연히 현업에서 유리하다고 생각합니다.

 

이것이 갖춰진 개발자와 그렇지 않은 개발자가 동일한 일을 받았고,

그 일이 이런 개선을 요구한다면 어떻게 될까요?

아마 전자는 개선해서 결과를 낼 것이고, 후자는 연산이 오래 걸려서 못한다고 할 수도 있습니다.

이것은 일이 되느냐 마느냐를 결정하는 중요한 포인트입니다.

위에서 풀어놓은 이야기가 필요 없다고 생각할지라도 이런 생각을 한 번쯤 해볼 필요는 있겠습니다.

 

"이것은 난제인가, 아니면 내가 모르는 것일 뿐인가?"