[자료구조] 알고리즘 성능 분석 - 시간복잡도, 공간복잡도, 빅오표기법

효율적인 알고리즘이란 전체 실행 시간이 짧으면서 메모리와 같은 컴퓨터의 자원들을 적게 사용하는 알고리즘 이다. 

일반적으로 메모리 공간보다 실행시간이 더 중요하게 생각된다. 그렇다면 실행시간을 측정하기 위해 어떤 방법을 써야할까? 두 개의 알고리즘을 동시에 실행에 비교를 하는 경우에는 무조건 "구현"해야하고, 동일한 조건의 하드웨어여야하고, 소프트웨어환경도 동일해야하기 때문에 효율성을 따지기에 요구사항이 많다. 이와같은 문제점들 때문에 알고리즘을 직접 구현하지 않고도 대략적인 효율성을 분석할 수 있는 방법이 개발되었다. 이것을 알고리즘의 복잡도라고 하고, 알고리즘의 실행시간 분석은 시간 복잡도(time conplexity), 알고리즘이 사용하는 기억 공간 분석을 공간 분석도(complexity)라고 한다.

 

[시간복잡도]

시간 복잡도는 알고리즘의 절대적인 실행시간을 나타내는 것이 아니라 알고리즘을 이루고 있는 연산들이 몇 번이나 실행되는지를 숫자로 표시한다. 연산에는 산술 연산, 대입 연산, 비교 연산, 이동 연산 등 이 모두 포함되고, 이들 연산의 실행횟수를 복잡도 분석에 사용한다. 

 

어떤 알고리즘을 실행하는데 필요한 연산의 수는 보통 입력의 개수 n에 영향을 받는다. 이와 같이 연산의 수를 n의 함수로 나타낸 것을 시간 복잡도 함수라고 하고 T(n) 이라고 표기한다. 

 

function find_min(arr:array,n:int): 

     minValue = 1NF                  ①

     loop i = 0 부터 n-1 까지:        

          if arr[i] < minValue:        ②

               minValue = arr[i]      ③

     return minValue                 ④

 

위의 유사코드(pseudo-code)의 T(n)을 구해보자!!

 

명령어	최대횟수
①	1
②	n
③	n
④	1
total	2n+2

 

T(n) = 2n+2 이다. 

 

 

 

[빅오 표기법]

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법

빅오 표기법는 알고리즘의 시간 복잡도를 O(n) "빅오 of n" 이라고 하고 정의는 다음과 같다. 

만약

이면, 위의 조건을 만족시키기 때문에

이다!!!!

 

빅오표기법은 데이터 입력값(n)이 충분히 크다고 가정하고 있고, 알고리즘의 효율성 또한 n의 크기에 따라 영향받기 때문에 상수항 또는 영향력이 없는 항들은 무시한다. 이렇게 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간 복잡도를 간단하게 표시할 수 있다. 

 

 

[빅오 표기법 종류]

다음은 많이 사용되는 빅오 표기법을 복잡도 순으로 표시한 것이다. 

아래로 갈수록 실행시간은 늘어난다!!!

 

 

 

그 밖에 빅오메가 표기법과 빅세타 표기법이 있다. (보통 3개 중에 빅오 표기법을 주로 사용한다)

이 두 가지 표기법은 다음 시간에!!!