[Data Structure/자료구조] 시간복잡도/공간복잡도

시간복잡도와 공간복잡도에 대해 설명해 주세요.

• 알고리즘의 성능 평가를 위한 척도라고 할 수 있다.
• 알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'의 척도를 사용하는데, 이때 시간복잡도와 공간복잡도가 사용된다. 복잡도가 낮을수록 좋은 알고리즘으로 평가한다.
  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리(공간) 사용량 분석

 

시간복잡도 표기법 빅오, 빅오메가, 빅세타를 설명해 주세요.

Big-O(빅 오) 표기법

• 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다.

Big-Ω(빅 오메가) 표기법

• 알고리즘 최상의 실행 시간을 표기한다.

Big-θ(빅 세타) 표기법

• 알고리즘 평균 실행 시간을 표기한다.

 

다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?

• 알고리즘의 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.

 

O(1)은 O(N^2) 보다 무조건적으로 빠른가요?

• 그렇다고 볼 수  있습니다.
• O(1)
  입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 나타냅니다. 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않습니다.
• O(n^2)
  데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘입니다. 예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 됩니다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직합니다.