[알고리즘] 계산복잡도 - 시간복잡도, 공간복잡도

계산복잡도 : 어떤 알고리즘이 문제를 풀기위해 해야하는 계산이 얼마나 복잡한지를 나타낸 정도를 말한다. 즉, 알고리즘의 성능, 효율을 측정하기 위한 것이다. 계산 복잡도는 특별한 언급이 없다면 시간 복잡도를 의미하는 것이지만 본래 계산 복잡도는 시간 복잡도(time complexity), 공간 복잡도(space complexity)로 두가지가 있다. 계산 복잡도를 표현하는 방법에는 여러가지가 있는데 그 중 대표적인 표기법은 대문자 O 표기법(Big-O 표기법) 이다.

시간 복잡도 : 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석한 것.

• O(n) : 알고리즘에 필요한 연산 횟수가 입력 크기 n과 비례할 때. 
• O(1) : 알고리즘에 필요한 연산 횟수가 입력 크기 n과 무관할 때.

예를 들어 0부터 n까지의 합을 더한다고 하자. 이 계산을 할 수 있는 방법에는 두가지가 있다. 첫 번째로 0+1+2+ ... + n 과 같이 직접 모두 더하는 방법과 n(n+1)/2 의 공식을 이용하는 방법.  첫 번째 방법을 이용하면 연산을 n번 해야하고, 두 번째 방법을 이용하면 n의 값과 상관 없이 덧셈, 곱셈, 나눗셈 한 번씩, 총 세번의 연산이 필요하다.  첫 번째 알고리즘은 연산이 n번 일어나므로 n의 값에 따라 시간 복잡도도 달라진다. 따라서 시간복잡도는 O(n) 이 된다. 두 번째 알고리즘은 연산횟수가 n의 값과 상관 없이 이루어지므로 시간복잡도는 O(1)이 된다. 

공간 복잡도 :  어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억장소)가 필요한지 분석한 것.

 

Big-O 표기법

• 복잡도 =  n^2 + 2n + 9 일 때 → O(n^2)
• 복잡도 =  n^4 + n^3 + n^2 일 때 → O(n^4) 
• 복잡도 =  5n^3 + 2n^2 +1 일 때 → O(n^3)

이와 같이 계산복잡도를 계산한 것(연산횟수)의 최고차항의 차수가 빅오가 된다.