시간복잡도와 공간복잡도 개념. 알고리즘 초보라면 필독!!

알고리즘 공부를 시작함에 있어서 시간복잡도와 공간복잡도의 개념은 알고리즘 평가의 기본이 되는 개념입니다.

규모가 크거나 매우 복잡한 컴퓨터 프로그램을 개발할 때는 해결해야 할 문제를 제대로 이해해서 정확히 정의하고, 그 복잡도를 관리하고 구현하기 쉬운 작은 작업으로 분리하는데 가장 많은 노력이 투자되어야 합니다.

그러기 위해서는 복잡도 분석을 할 수 있어야합니다. 그렇기 때문에 알고리즘 평가의 기본이 되는 개념이 복잡도 개념인 것입니다.

복잡도의 개념은 크게 두 가지가 있습니다. 바로 시간복잡도 (Time Complexity) 와 공간복잡도 (Scpae Complexity)입니다. 재밋게도 저 둘은 사람들에게도 가장 중요한 자원들입니다. 이 두 자원을 어떻게 관리하냐가 알고리즘과 더 나아가서 프로젝트 전체의 승패를 좌우합니다.

---

시간복잡도 (Time Complexity)

• 알고리즘을 실행하여 종료하기 까지의 시간

명령어의 실제 실행시간을 제외한 명령어의 실행횟수(대입연산)를 고려하는 것이 일반적입니다.

그럼 시간복잡도 계산하는 예시를 하나 보도록 하겠습니다. 코딩언어는 c++ 입니다.

int sum(int a[], int b)
{
  int c = 0;                    // 1
  for(int i = 1, i <= b, i++)   // b (i에 대입이 b번 일어나게 된다)
  {
    c += a[i];                    // b (c에 대입이 b번 일어나게 된다)
  }
  return c;                     // 1
}
// 총 2b+2 의 시간복잡도를 가지게 된다. 

---

공간복잡도 (Space Complexity)

• 알고리즘을 실행하여 종료할때까지 필요한 기억장치의 크기

알고리즘이 수행될 때 사용하는 메모리의 최대치를 일반적으로 표시합니다. 사실 메모리라는 것이 요즘처럼 시스템 자원이 풍부한 시기에는 그 중요도가 시간복잡도에 비해서 떨어지게 됩니다. (시간은 아직까지도 그 누구에게나 공평하니까 아낄수록 좋음) 그래도 자원은 아낄 수 있으면 아끼는게 좋스습니다.

공간복잡도를 계산하는 예시 하나를 보도록 하겠습니다.

int sum(int a[], int b)
{
  int c = 0;                    // b 와 c 의공간 2
  for(int i = 1, i <= b, i++)   
  {
    c += a[i];                    // b (a[]를 b만큼 저장하기 위한 공간)
  }
  return c;                     
}
// 총 b+2 의 공간복잡도를 가지게 된다. 

---

알고리즘을 평가할 때 시간복잡도와 공간 복잡도는 무조건 평가하게 됩니다. 고급 알고리즘 개념으로 넘어갈 수록 이러한 한정된 자원을 얼마나 잘 활용하는가를 평가하기 때문에 알고리즘을 더욱 깊게 공부하거나 효율적으로 알고리즘을 적용하고 싶을때 복잡도 개념에 대한 숙지는 필수 입니다.

복잡도 개념을 고려하여 구현한 알고리즘과 아닌알고리즘의 차이는 시작부터 각도가 달라져 알고리즘이 진행될수록 그 차이가 걷잡을 수 없이 커지게 됩니다. 처음부터 알고리즘을 고려하여 고급진 알고리즘을 구현하시길 바랍니다!!