[알고리즘] 시간복잡도와 공간복잡도, Big O

Why?

자료구조와 알고리즘을 공부하면서 마주쳤던 복잡도..
"몰라도 문제 푸는 데 지장 없지!"라고 생각하며 애써 외면해 왔지만
문제를 푸는 과정에 많은 시간 초과를 겪으며, 복잡도를 이해할 필요성을 느꼈다.

복잡도(Complexity)

알고리즘의 성능 및 효율성을 나타내는 척도로
시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다.
복잡도를 나타내는 방법으로 빅 오(O), 오메가(Ω), 세타(Θ)가 있으며, 주로 빅 오와 세타 표기법이 많이 사용된다.

코딩 문제를 풀면서 시간제한과 메모리 제한을 두는데,
시간에 해당하는 것이 시간복잡도, 메모리에 해당하는 것이 공간복잡도이다.
이 두 가지를 고려하여 문제를 풀어야 한다.

1️⃣ 시간복잡도(Time Complexity)

입력값의 변화에 따라 연산을 실행할 때, 필요한 연산의 횟수를 나타낸다.
언어마다 같은 코드를 작성해도 실행 시간이 다르므로, 연산 횟수를 기준으로 나타낸다.

예시

양수 정수 n을 n번 더하는 계산을 코드로 작성할 때
모든 연산의 소요시간이 t로 같다고 가정한 경우, 아래 2개의 코드는
Case 1는 2t만큼, Case 2는 (2n+1)t만큼 시간이 필요하다.

// Case 1
int sum = n*n;

// Case 2
int sum = 0;
for(int i=1; i<n; i++)
	sum += i;

연산의 종류	Case 1	Case 2
대입 연산	1	n + 1
덧셈 연산	0	n
곱셈 연산	1	0
천제 연산 횟수	2	2n + 1

2️⃣ 공간 복잡도(Space Complexity)

프로그램을 실행시킨 후 완료하는 데 필요로 하는 공간(메모리)의 양으로, 배열의 크기, 동적 할당, 재귀 함수 등이 공간 복잡도에 영향을 미친다.

고정 공간과 가변 공간의 합으로 표현한다.
고정 공간: 코드 저장공간, 단순 변수, 고정크기의 구조변수, 상수
가변 공간: 문제 해결을 위한 알고리즘이 필요로 하는 공간, 함수가 순환 호출을 할 때 요구되는 공간, 즉 동적으로 필요한 공간

예시

팩토리얼 함수를 구현하는 경우, 반복문 또는 재귀를 이용할 수 있다.
반복문에 경우 factorial함수 하나만 스택에 쌓이게 되고, 공간 복잡도는 O(1)이다.
재귀에 경우 factorial 함수가 n이 1이 될 때까지 호출되므로 스택에 n개가 쌓여, 공간 복잡도가 O(n)이다.
O는 빅오 표기

// 반복문을 이용한 코드
int factorial(int n){
	int answer = 1;
    for(int i=1; i<n; i++){
    	answer = fanswer * i;
    }
    return answer;
}

// 재귀를 이용한 코드
int factorial(int n){
	if(n==1) return 1;
    return n * factorial(n-1);
}

3️⃣ 빅오 표기법(Big-O notation)

복잡도는 최악, 최선, 평균의 경우를 기준으로 표기할 수 있다.
Big-O(빅-오): 최악 -> 상한 점근
Big-Ω(빅-오메가): 최선 -> 하한 점근
Big-θ(빅-세타): 평균 -> 그 둘의 평균

빅오 표기법(Big-O notation)은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.
빅오 표기법은 최악의 경우를 고려하기 때문에, 최악의 시간까지 고려할 수 있다.

사용 이유

최선의 경우 1초, 평균 1분, 최악 1시간이 걸려 결과를 반환하는 알고리즘을 구현했고, 최선의 경우를 고려한다 가정했을 때,
이 알고리즘을 10번 실행한다면, 최선의 경우 10초, 평균 10분, 최악 10시간이 걸린다.
그러나 알고리즘을 실행해 5시간이 걸린다면, 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해 알고리즘을 다시 파악해야 하는 문제가 생긴다.
이러한 문제를 방지하기 위해 최악을 고려하여 알고리즘을 작성한다.

빅오 표기법의 특징

상수항과 영향력 없는 항을 무시한다.

• 빅오 표기법은 n이 충분히 크다고 가정하여 작성한다.
• 알고리즘은 n의 크기에 영향을 받으므로, 상수항 같은 사소한 부분은 무시한다.
  O(2n)은 O(n)으로 표기한다.
• 영향력이 큰 항 이외에 영향력이 없는 항은 무시한다.
  O(n2 + 2n + 1)은 O(n2)으로 표기한다.

빅오 표기법의 종류 및 예시

slower로 갈수록 효율성이 떨어진다.
1. O(1): 스택의 push / pop
2. O(log n): 이진트리
3. O(n): for 문
4. O(nlog n): 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
5. O(n2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2n): 피보나치 수열
faster O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(2n) slower

시간복잡도와 빅오 표기법

입력(n)을 기준으로 연산의 횟수를 기준으로 표기한다.
단, 모든 연산의 횟수가 아닌 알고리즘에서 핵심이 되는 연산의 횟수만을 이용한다.

// Case 2
int sum = 0;
for(int i=1; i<n; i++)
	sum += i;

위의 예시(Case 2)에 경우 (2n+1)t만큼의 시간이 필요하다.
수식에 포함된 n이 커지게 되면 n에 비례하게 되므로 O(n)로 표기한다.

공간복잡도와 빅오 표기법

알고리즘 실행에 메모리가 얼마나 사용되는지를 계산하면 된다.
크기가 n인 배열을 입력으로 주었을 때, 알고리즘이 n * n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 O(n2)이다.
공간복잡도는 위의 예시에서 한 번 다뤘으니 읽어보면 된다.

참고자료

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법
[알고리즘] 복잡도란 무엇인가(시간복잡도, 공간복잡도, 빅오 표기법)
[알고리즘] Time Complexity (시간 복잡도)
시간복잡도와 공간복잡도(Time Complexity Space Complexity)
[Algorithm] 시간 복잡도, 공간 복잡도