[알고리즘] 시간복잡도와 공간복잡도, 빅-오(Big-Oh) 표기법

안녕하세요, katte입니다.

이번 글에서는 알고리즘을 평가하는 기준인 시간복잡도와 공간복잡도, 그리고 시간복잡도를 나타내기 위한 방법인 빅-오 표기법에 대해 알아보도록 하겠습니다.

알고리즘을 평가하는 기준으로는 시간복잡도와 공간복잡도 두 가지가 있습니다.

일반적으로는 공간복잡도보다 시간복잡도를 더 우선시합니다.

시간복잡도의 경우에는 데이터 양에 따른 연산 횟수와 관련이 있습니다.

즉, 데이터의 양이 n일 때, 연산횟수 T(n)이 어떤 형태를 띄는가에 관심을 둡니다.

이때 중요한 것은, 데이터 양 n이 증가함에 따라 T(n)이 어느 정도의 속도로 증가하는가 입니다.

데이터의 양이 적을 때는 어떤 알고리즘이든 속도가 크게 차이나지 않지만, 데이터의 양이 증가하면 이야기가 달라지기 때문입니다.

따라서 비록 데이터의 양이 적을 땐 효율적이더라도, 데이터의 양이 증가함에 따라 연산횟수가 기하급수적으로 증가하는 알고리즘은 좋은 알고리즘이라고 할 수 없겠죠.

또한 알고리즘을 평가할 때는 항상 최악의 경우(worst case)를 따지게 됩니다.

최상의 경우는 의미가 없고, 평균적인 경우는 구하기 어렵기 때문입니다.

예를 들어, 데이터의 수가 n일 때, 최선의 경우 연산횟수가 1이고 최악의 경우 연산횟수가 n인 알고리즘의 T(n)은 n이라고 할 수 있습니다.

데이터 수에 대한 연산횟수 T(n)은 빅-오 표기법(Big-Oh Notation)을 통해 간략화 할 수 있습니다.

빅-오 표기법은 함수 T(n)에서 가장 영향력이 큰 부분만을 따지는 것입니다.

예를 들어 T(n)=n^2+2*n+1이라면, 이 중 가장 영향력이 큰 n^2만 따져 O(n^2)이라고 표기하게 됩니다.

영향력 순서는 다음과 같습니다.

O(1) < O(log(n)) < O(n) < O(n*log(n)) < O(n^2) < O(n^3) < O(2^n)

즉, T(n) = 7*n^3 + 3*n^2 + 2 와 같은 경우엔 n^3이 가장 영향력이 크므로 O(n^3)이 되고,

T(n) = 2^n + n^2 와 같은 경우엔 O(2^n)이 되는 것이죠.

기본적으로 상수 < 로그 < 1차식(선형) < 1차식*로그(선형로그) < n차식 < 지수 라고 이해하시면 될 것 같습니다.

대표적인 빅-오는 같습니다.

O(1) 상수형 빅-오: 데이터 수에 상관없이 연산횟수가 고정이라는 것을 의미
O(log(n) 로그형 빅-오: 데이터 수의 증가율에 비해 연산횟수의 증가율이 훨씬 낮은 알고리즘. 바람직한 유형임
O(n) 선형 빅-오: 데이터 수와 연산횟수가 비례하는 경우
O(n*log(n)) 선형로그형 빅-오: 데이터 수가 2배가 될 때 연산 횟수가 2배보다 조금 더 증가하는 경우
O(n^2): 연산횟수가 데이터수의 제곱이 되는 경우로, 데이터의 양이 많은 경우에는 부적절하다. 주로 반복문이 이중으로 중첩된 경우에 발생. 즉 알고리즘적 측면에서 중첩된 반복문은 바람직하지 않다고 할 수 있다.
O(n^3): 연산횟수가 데이터수의 세제곱이 되는 경우로, 주로 삼중으로 중첩된 반복문에서 발생. 역시 일반적으로 사용하기엔 무리가 있다
O(2^n) 지수형 빅-오: 사용하기에 매우 무리가 있다.

* 해당 글은 '윤성우의 열혈 자료구조'를 참고하여 작성되었습니다.

티스토리툴바