시간복잡도 & 공간복잡도

등장 배경

---

• 코드의 성능, 효율성을 판단할 기준이 필요했다.
• 실제 실행시간과 메모리 사용량을 측정한다면?
  • 하드웨어의 성능, 소프트웨어(운영체제)의 성능, 호환성 등 외부 요인이 작용하여 동일한 기준으로 비교할 수 없다.
  • 미완성 코드는 실행이 불가능하므로 측정이 불가능하다.

→ 다른 요인과 무관하게 입력 크기에만 영향을 받는 이론적 시간 측정 방법을 만들었다.

 

 

시간복잡도

---

• 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.
• 점근 표기법을 이용하여 나타낸다.

💡 점근 표기법이란, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법을 말한다.

• 단위 연산의 횟수를 기준으로 계산한다.

💡 단위 연산(primitive operation)이란, 정의, 단순 계산, 비교, 출력 등의 가장 간단한 연산들을 말한다.

 

Big-O notation(빅 오 표기법)

• O(N) 의 형태로 나타낸다.
• 가장 많이 쓰는 표기법이다.
• 단위 연산이 가장 많이 실행되는 최악의 경우, 가장 느린 실행 시간(worst-case)을 의미한다.
• Big-O의 대표적인 예시
  • O(1) : 단위 연산, 입력의 크기가 영향을 미치지 않는 경우
  • O(N) : N번 반복하는 경우 (for 문이 대표적)
  • O(log2 N) : 이진탐색
  • O(N^2) : 이중 반복문, 버블정렬
  • O(Nlog2N) : 병합정렬, 힙정렬
  • O(2^N) : 재귀(피보나치, 하노이 탑 등)

 

Big-Omega notation(빅 오메가 표기법)

• Ω(N) 의 형태로 나타낸다.
• Big-O 와 반대로 단위 연산이 가장 적게 실행되는 최선의 경우, 가장 빠른 실행 시간(best-case)을 의미한다.

※ Big Omega를 잘 쓰지 않는 이유?
☞ 시간과 공간의 제약, 즉 상한선에 초점을 두고 있기 때문에 대부분 최악의 경우를 고려한다.

 

Big-Theta notation (빅 세타 표기법)

• Θ(N) 의 형태로 나타낸다.
• 최악과 최선의 중간인 평균 적인 경우를 의미한다.
• Big-O와 Big-Omega를 동시에 만족하는 경우에 해당한다.
  • 시간복잡도가 O(N) 이면서, Ω(N) 이면 Θ(N) 이라고 할 수 있다.

 

 

 

공간복잡도

---

• ‘얼마나 많은 메모리를 사용하는 지’를 의미한다.
• 시간복잡도와 마찬가지로 Big-O 표기법을 사용한다.
• 기술의 발달로 인해 메모리에 여유가 생겼다.
  • 따라서, 공간복잡도는 거의 고려하지 않는다.
• 대용량 데이터, 빅 데이터를 다루는 경우에 공간복잡도를 고려한다.

 

 

추가 질문

---

Q. O(1)이 O(N)보다 무조건적으로 빠른가요?

복잡도를 계산할 때는 입력 크기 N이 무한대로 향한다고 생각하기 때문에, 상수를 무시한다.

• ex) O(3*N) = O(N), Ω(10logN) = Ω(logN)

마찬가지로 O(1000)은 O(1)로 표기한다. 동시에 N<1000 이면, O(1)은 O(N) 보다 느리다.