[자료구조] 알고리즘의 복잡도란?

1. 복잡도(Complexity)란

각종 자료구조를 사용해 문제를 해결한 알고리즘을 개발했다고 하자. 이러한 알고리즘은 복잡도라는 지표에 의해 "효율적"인가를 판단할 수 있다.

알고리즘이 실행되는 데 필요한 리소스의 양을 설명하는 개념

• 시간복잡도와 공간복잡도를 활용해 알고리즘이 실행되는 데 필요한 시간과 메모리 공간을 평가하여 알고리즘의 효율성을 판단
• 시간복잡도는 시간의 효율성, 공간복잡도는 공간(메모리)효율성을 의미
• 알고리즘의 복잡도를 토대로 알고리즘의 선택 및 개선, 시스템 설계 등에 효율적인 결정

1) 시간 복잡도(Time Complexity)

알고리즘이 입력 데이터의 크기에 따라 실행되는 데 걸리는 시간을 분석
즉, 알고리즘이 수행되는 데 "시간이 얼마나 소요" 되는가를 나타냄

• 따라서 시간 복잡도가 작을수록(=덜 복잡할수록) 효율적인 알고리즘
• 같은 문제도 어떤 자료구조, 어떤 알고리즘을 사용하는지에 따라 시간복잡도가 달라짐

① 표기법
: 알고리즘의 시간 복잡도를 수치화해서 나타내는 방법

• Big-O(빅-오) : 상한 접근
• Big-Ω(빅-오메가) : 하한 접근
• Big-θ(빅-세타) : 그 둘의 평균

즉, 각각 최악, 최선, 평균의 경우 걸리는 시간을 나타냈다고 볼 수 있음

② 빅오 표기법

• 입력 데이터(n)을 기준으로 연산 횟수를 나타냄
• 예시

for(int i=0;i<10;i++){
	for(int j=0;j<n;j++){
    	for(int k=0;k<n;k++){
        	if(true)cout<<k<<'\n';
         }
     }
 }
 for(int i=0;i<n;i++){
	if(true) cout<<i<<'\n';
}

입력으로 부터 출력을 계산해는 데 필요한 연산의 횟수 : $10n^2 + n$

-> '가장 많은 영향을 끼치는 항의 상수 인자를 빼고 그 외 항을 제거'

-> 시간 복잡도 : $O(n^2)$

③ 시간 복잡도 속도 비교

위로 갈수록 더 나은(빠른, 효율적인) 알고리즘이라고 할 수 있다.

2) 공간 복잡도(Space Complexity)

알고리즘이 실행되는 동안 사용되는 메모리 공간의 양을 분석

① 공간 복잡도 계산

int a[1004];

이 경우 4byte인 int 자료형이 1004개의 배열을 이루고 있으므로 10004 x 4 byte의 공간을 사용한다고 러프하게 볼 수 있다.

따라서 결론은 문제 상황에 적합한 적절한 자료구조와 함수를 통해 효율적인 알고리즘을 구현함으로써 시간복잡도와 공간복잡도를 줄일 수 있다. 제대로된 프로그래머라면 이러한 퀄리티적인 측면에 집중할 필요가 있다.

사실 알고리즘은 best를 찾기보다 worst를 피하는 것이 더 현실적일 수 있으나, 끊임없이 고민하다 보면 보다 빠르게 이상적인 알고리즘에 도달할 수 있을것이다.