자료구조와 알고리즘 성능 평가 요소

구현이 아닌 성능이 목적이라면 각 자료구조와 알고리즘의 성능을 분석하고 평가할 수 있어야 한다.
이를 평가하는 두 가지 요소로 시간복잡도와 공간복잡도가 있다.
시간복잡도는 속도에 대한 분석결과를 가리키며, 공간복잡도는 메모리 사용량에 대한 분석결과를 가리킨다.
우리는 보통 시간복잡도에 관심이 더 많다.

시간복잡도

시간복잡도는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다.

실질적인 run-time을 비교하는 것이 아닌, 하드웨어, 또는 소프트웨어의 환경에 상관없이 데이터나 사용자의 증가율에 따른 성능을 예측한다.

보통 연산을 적게 하는 알고리즘일수록 속도가 빠르며 좋은 알고리즘이라 할 수 있다.

평가기준

알고리즘에는 최선의 경우, 평군적인 경우, 최악의 경우가 존재한다.
보통 시간복잡도를 평가하는 정보로 최악의 경우를 사용한다.

Big-O표기법

성능을 수학적으로 표현해주는 표기법으로서, 대표적으로 Big-O표기법을 사용한다.
데이터의 수 n과 그에 따른 시간복잡도 함수를 T(N)이라 할 때, T(N)의 최고차항 차수만을 남겨 표기하는 것이 Big-O 표기법이다.

데이터 수	T(N)	Big-O
n	3n+2	O(n)
n	7n³+3n²+2	O(n³)
n	2ⁿ+n²	O(2ⁿ)
n	n+㏒n	O(n)
n	n+n㏒n	O(n㏒n)
n	2ⁿ+n³	O(2ⁿ)

대표적인 Big-O

• O(1)
  - 상수형 Big-O라 한다. 이는 데이터의 수에 상관없이 연산횟수가 고정인 유형의 알고리즘을 뜻한다.
• O(㏒n)
  - 로그형 Big-O라 한다. 데이터의 수의 증가율에 비해 연산횟수의 증가율이 매우 낮다.
• O(n)
  - 선형 Big-O라 한다. 데이터의 수와 연산횟수가 비례한다.
• O(n㏒n)
  - 선형로그형 Big-O라 한다. 이는 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가한다.
• O(n²)
  - 데이터 수의 제곱에 해당하는 연산횟수를 요구한다. 이중 반복문의 시간복잡도가 O(n²)이다.
• O(n³)
  - 삼중 반복문의 시간복잡도가 O(n³)이다.
• O(2ⁿ)
  - 지수형 Big-O라 한다. 연산횟수의 증가가 엄청나기 때문에 사용하기에 비현실적인 시간복잡도이다.

참고

윤성우의 열혈 자료구조