알고리즘 (1) : 시공간 복잡도

목표

1. 빅오 표기법의 개념
2. 시간 복잡도, 공간 복잡도란
   
   
   

빅오(Big-O)표기법이란

빅오는 시공간 복잡도를 수학적으로 표현하며 점근적 표기법중의 하나이다. 알고리즘의 성능을 논리적으로 예측하기 위해 사용하며, 코드의 실제 러닝 타임을 나타내는 것이 아니다. Input 데이터 증가율에 따른 알고리즘의 성능을 평가하는 지표가 되어준다. 이러한 빅오 표기법으로 측정되는 복잡성에는 시간과 공간 복잡도가 있다.

규칙

• 가장 높은 차수만 남긴다
  O(2n² + n) -> O(n²)
• 계수 및 상수는 버린다.

일반적인 순서
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

시간복잡도, 공간 복잡도

시간 복잡도
시간 복잡도란 빅오에 대한 시간 개념으로 알고리즘의 수행 시간을 말한다. 수행되는 연산의 수와 비례하여 실행시간이 증가하게되고 개발자가 짠 코드의 실행시간에 대하여 성능적으로 얼마나 효율적인지 평가하는 지표가 된다.

공간 복잡도
공간 복잡도란 공간에 대한 개념으로 알고리즘이 메모리(공간)을 얼마나 필요로 하는지를 말한다. 주로 자료구조에서 자주 등장하는 개념으로 코드가 얼마나 메모리 공간을 효율적으로 사용하는지에 대한 평가 지표이다. 최근 컴퓨터의 성능이 발전하며 시간복잡도에 비해서는 덜 중요하게 보일 수 있으나 함수의 재귀 호출로 구현한 알고리즘 또는 자료구조에 효율성을 고민해야하는 상황에서는 고려가 필요하다.