시간 복잡도 & 공간 복잡도

1. Algorithm

• 알고리즘을 평가할 때, 알고리즘의 효율성을 판단할 때 시간 복잡도와 공간 복잡도를 사용한다.
• 시간 복잡도와 공간 복잡도는 주로 점근적 표기법 중 빅 오 표기법을 이용하여 나타낸다.
• 이유는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해 볼 수 있기 때문이다.

 

2. 시간 복잡도(Time Complexity)

• 어떤 명령을 수행하는 데 걸리는 총 연산의 횟수를 의미한다.
• 해당 알고리즘이 얼마나 빨리 수행되는지를 의미한다.
• 시간 복잡도가 커질수록 알고리즘이 더 느린 것을 말한다.

시간 복잡도는 3가지 경우로 나타낸다.

 

1) 최선의 경우(Best Case)

• 빅 오메가 표기법 사용
• 최선의 시나리오로 최소 이만한 시간이 걸림

2) 최악의 경우(Worst Case)

• 빅 오 표기법 사용
• 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림

3) 평균적인 경우 (Average Case)

• 빅 세타 표기법 사용
• 평균 시간을 나타낸다.

평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어렵고,

최악의 경우까지 파악을 해야 신뢰도가 올라가기 때문에 보통 최악의 경우로  알고리즘의 성능을 파악한다.

 

3. 공간 복잡도(Space Complexity)

• 어떤 명령을 수행하는 데 필요한 메모리의 크기를 말한다.
• 해당 알고리즘이 얼마나 적은 메모리 사용하는지를 의미한다.
• 공간 복잡도가 커질수록 메모리를 많이 차지하는 것을 의미한다.

 

• 가장 이상적인 프로그램은 시간 복잡도와 공간 복잡도가 모두 낮은 것이지만, 시간 복잡도와 공간 복잡도는 반비례한다.
• 두 개의 가치 중 한 가지를 일부 포기해야만 하는(trade-off) 상황이 항상 생기는데 결론적으로 얘기하자면 일반적인 상황에서 우리는 시간 복잡도를 우선으로 생각해야만 한다.
• 예를 들어 하나의 알고리즘이 수행되는데 10일이라는 시간이 걸리지만, 메모리의 여유가 있는 상태이며, 메모리를 더 많이 쓴다면 시간을 10일에서 1일까지 줄일 수 있다고 가정해 본다면,
• 시간은 돈을 주고도 살 수 없지만 메모리는 부족하면 추가로 달기만 하면 된다.
• 또한 현대의 하드웨어는 성능이 많이 발전했고, 또한 계속 발전하기 때문에 기본적으로는 시간 복잡도를 우선으로 생각해야 한다.
• 또한 일반 개발자들은 평소 메모리의 부족을 느낄 일이 사실상 없다고 봐도 무방하다.

 

4. 시간 복잡도의 중요성

일반적인 프로그래밍에서의 공간 복잡도는 크게 중요하지 않다. 하드웨어의 발달로 대체를 할 수 있기 때문이다. 하지만 시간 복잡도의 경우 어떠한 로직을 구현할 때 잘못된(시간 복잡도가 크면) 알고리즘을 사용한다면, 시간은 1초가 될 수도 있지만 10초, 1분…으로 늘어날 수 있고, 시간은 한정된 자원이고 하드웨어처럼 업그레이드를 하지 못하므로 시간 복잡도와 공간 복잡도에 대한 이해와, 시간 복잡도를 낮추는 게 중요하다고 할 수 있다. 물론 임베디드처럼 제한된 메모리 환경이라던지 대규모 데이터처리 환경에서는 공간 복잡도도 중요하게 생각해야 한다.