알고리즘의 성능 분석(Big-O)

알고리즘(algorithm)이란?

주어진 문제를 유한한 시간 내에 해결하는 단계적 절차이다.
단계적으로 해결하기 위해 자료구조(data structure)라는
데이터를 조직하고 접근하는 체계적 방식에 대해 학습한다.

어떤 알고리즘이 좋은 알고리즘일까?

1. 직관적인 알고리즘
2. 속도가 빠른 알고리즘
3. 메모리 공간이 효율적인 알고리즘
4. 범용성이 넓은(유지,보수가 쉬운) 알고리즘

내가 설계한 대로 정확하게 작동하는 것이 가장 중요하다.
정확성이 보장이 되었다면 다음으로 속도가 빠르고, 메모리 공간을 많이 차지하지 않는지도 고려해야 한다. 속도(시간)와 메모리(공간)를 고려한 것이 바로 계산 복잡도이다.

알고리즘 계산 복잡도

알고리즘의 계산 복잡도는 시간 복잡도(time complexity)와 공간 복잡도(space complexity)를 고려하여 평가한다. 알고리즘의 정확성은 보장된다는 가정 하에 속도가 빠르고, 메모리 사용량이 적은 알고리즘이 좋은 알고리즘이라는 것이다.
하지만 보통 알고리즘을 평가할 때는 시간 복잡도에 초점을 둔다.
시간과 공간은 반비례하는 경향이 있어 두 마리 토끼를 둘 다 잡기란 쉽지 않을 뿐더러 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도에 초점를 중요시하기 때문이다. 그래서 우리는 시간 복잡도를 측정하는 방법에 대해 알아야 한다.

시간 복잡도

우리가 작성한 코드는 실행시간이 얼마나 걸릴까?
시간 복잡도는 연산 횟수를 통하여 계산할 수 있다.
연산 횟수(알고리즘의 실행시간) 상황마다 다르고 최선의 상황과 최악의 상황으로 나눌 수 있다.
항상 최선의 상황만 나오리라는 보장은 없으므로 최악의 상황까지 고려하여 알고리즘을 설계해야 한다. 따라서 시간 복잡도를 계산할 때는 최악의 상황이 기준이 된다.

연산횟수 계산

위 그림은 의사코드를 조사하여 알고리즘에 의해 실행되는 연산횟수의 maximum을 입력크기의 함수형태로 결정하였다.
이 의사코드의 경우 최악의 경우 7n - 2의 비교연산 횟수가 나온다.

그렇다면 위 코드의 시간 복잡도는 T(n) = 7n - 2일까?
위 코드의 시간 복잡도 T(n) = n이다.
이렇게까지만 하면 한가지 의문점이 생긴다.
비교 연산 횟수가 7n - 2이니까 T(n) = 7n - 2 아닌가?
하지만 n의 계수와 -2는 중요하지 않다.
중요한 것은 데이터의 수 n이 증가함에 따라 비교연산의 횟수가 선형적으로 증가한다는 사실이다. (이것은 아래에서 좀 더 자세히 설명하겠다.)

우리는 데이터 수 증가에 따른 연산횟수의 변화 정도를 파악하기 위해 Big-O 표기법을 사용한다.

Big-O란?

알고리즘 성능을 수학적으로 표기해주는 표기법이다.
데이터 수 n에 따라 시간 복잡도 T(n)을 오차 없이 구하는 것은 쉽지 않기 때문에 증가율로 시간 복잡도를 표기하는 것이다. 쉽게 말하면 근사치를 구한다는 것이다.

이 식에서 첫 번째 조건문의 연산 횟수는 N^2, 두 번째 식은 N, 마지막 세 번째 식은 1로 연산 횟수는 N^2 + N + 1이 맞다. N이 작을 때는 N과 + 1이 연산 횟수에 영향을 미치겠지만 우리는 데이터 수 증가에 따른 연산횟수의 변화 정도를 파악하는 것이므로 N이 무한이 커졌을 때 상황을 봐야한다. 다음 그래프를 보면 조금 더 직관적인 이해가 가능하다.

N^2 + N + 1에서 N이 무한이 커졌을 경우 N과 상수항 1값은 연산횟수 변화율에 영향을 거의 미치지 않는다.
따라서 T(n) = N^2 + N + 1식에서 T(n) = N^2으로 간략화할 수 있는 것이다.
참고 예이다.

다양한 식의 데이터 증가율

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

n! + 2^n + n^2 + 3의 식의 O(n)은 n!이 된다.
그래프를 보면 n!의 증가율이 2^n과 n^2보다 훨씬 크니까!
n이 무한히 커졌을 때 2^n과 n^2값은 무시할 수 있을 만큼 영향력이 없다는 뜻이다.

그래프에 해당하는 자료구조, 알고리즘 예시

같은 코드를 시간 복잡도를 달리하여 구현해보기

1. 시간 복잡도 O(N^2)

for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = 0; j <= i; j++) { //O(n^2) -> i번씩 j번 반복문을 수행해야 함
			sum += X[j];
		}
		arr[i] = (double)(sum) / (i + 1);
	}

이중 for문이므로 시간 복잡도는 O(N^2)
값이 들어올 때마다 반복문을 첫 값부터 새로운 값까지 더한 후 평균 구하기

2. 시간 복잡도 O(N)

int sum = 0;
	for (int i = 0; i < N; i++) {
		sum += X[i];
		arr[i] = (double)sum / (i + 1);
	}

값이 들어오면 이전에 계산했던 누적합에 새로운 값을 더해 평균 구하기