알고리즘 성능 평가

예시

하나의 문제를 해결하는 데 알고리즘은 다양할 수 있다. 아래의 예시를 보자.

1부터 n까지의 합을 구하는 알고리즘을 만들어라 (n은 1보다 크거나 같다)

1. <반복문 사용> n을 1씩 늘리면서 전체 합에 계속 더한다.

public int getSum(int num) {
	int total = 0;
	for (int i = 1; i <= num; i++) {
		total += i;
	}
	return total;
}

2. n(n+1)/2 라는 공식을 이용한다.

public static int getSum2(int num) {
	int total = num * (num + 1) / 2;
	return total;
}

왠지 아래의 알고리즘이 더 빠를 것 같다. 반복문을 사용하지도 않고 공식에 n값을 대입하기만 하면 되니까. 변수도 위에서는 2번, 아래에서는 1번 선언하니까 메모리도 조금 사용하고...

이런 걸 정량화해서 비교하는 방법이 바로 알고리즘 성능 평가다.

알고리즘 성능 평가의 두 가지 기준

시간 복잡도

• 알고리즘 실행 속도

공간 복잡도

• 알고리즘이 사용하는 메모리 사이즈

요즘 우리가 사용하는 전자 기기들의 저장 공간이 커짐에 따라서 공간 복잡도보다는 시간 복잡도가 알고리즘 평가에 더 중요한 기준이 된다고 한다. 물론, 빅데이터처럼 엄청나게 많은 데이터를 다루는 경우에는 공간 복잡도도 중요하겠지만.

그리고 대체로 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있다.

우선, 이번 글에서는 "시간 복잡도"를 기준으로 정리해보자.

알고리즘 성능 표기법

• 여기서는 시간 복잡도를 기준으로 설명한다. 당연히 공간 복잡도도 표기법을 따른다.

"대략 이게 빠를 것 같네"라고 하지 않고, 정확하게 어느 정도 빠를 것 같은지는 어떻게 알 수 있을까? 다음과 같은 성능 표기법을 사용해서 알고리즘의 대략적인 실행 시간을 표시할 수 있다. N번 실행할 때의 시간 복잡도를 다음의 3가지 방법으로 나타낼 수 있다.

Bio-O 표기법 : O(N)

• 빅오 표기법
• 알고리즘 최악의 실행 시간을 표기
• 가장 일반적으로 사용함
• 아무리 최악의 상황이라도 이 정도 성능은 보장한다는 의미이기 때문

Ω 표기법 : Ω(N)

• 오메가 표기법
• 최상의 실행 시간 표기

Θ 표기법 : Θ(N)

• 세타 표기법
• 평균 실행 시간 표기

Big-O 표기법을 이용해서 시간 복잡도 비교하기

• 다음과 같은 순서대로 값의 크기를 비교할 수 있다. 즉, 속도를 비교할 수 있다. 시간 복잡도가 작을수록 알고리즘의 실행 시간은 짧고 속도는 빠르다!

  O(1) < O(logn) < O(n) < O(nlogn) < o(n²) < O(2n) < O(n!)

• 오랜만에 보는 log, 지수에 머리가 어질어질하다 🤪
• 시간 복잡도에서 log의 베이스는 2이다. 그니까 log2라는 뜻.
• ⭐️ 표현식에 가장 큰 영향을 미치는 n의 단위로 표기한다! (아래의 예시를 보며 이해해보자)

예시

1. (n이 아무리 커져도) 무조건 상수회 실행하는 경우 : O(1)

if (n < 10) {
System.out.println("10보다 작습니다");
}

• 반복문 0회 사용. n에 따라 알고리즘의 실행 횟수에 변화가 없다!

for (int i = 1; i < 3; i++) {
	System.out.println(n);
}

• 반복문 1회 사용. 반복문을 사용하긴 했는데 그냥 n을 3번 출력하기만 한다. n에 따라 n회 반복하는 등의 알고리즘의 실행 횟수에 따른 변화가 없다.

2. n에 따라 n회, n+10회, 2n-1회 등 실행하는 경우 : O(n)

• an + b (a, b는 상수, a≠0)

for (int i = 1; i < 3; i++) {
    for (int j = 1; j < n; j++) {
	// 중략
	}
}

• 이중 반복문인데, 하나는 상수회 반복, 하나는 n회 반복이다. n이 엄청 커지다 보면 상수회 반복하는 것은 의미가 없을 만큼 작기 때문에 n회 반복한다고 생각하는 것이다.

3. n에 따라 n2회, n2+100회, 3n2-10회 실행하는 경우 : O(n2)

for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
	// 중략
	}
}

• an2 + bn + c (a, b, c는 상수, a≠0)
• 둘 다 n회 반복하는 이중 반복문이다. n이 커짐에 따라 반복 횟수는 n2만큼 많아진다.

앞의 예시 다시보기

그럼 앞에서 1부터 n까지 더하는 알고리즘 예시를 다시 살펴보자.

public int getSum(int num) {
	int total = 0;
	for (int i = 1; i <= num; i++) {
		total += i;
	}
	return total;
}

• 입력값에 따라 입력값만큼 n회 반복하는 반복문이 1개 있다.
• 시간 복잡도 : O(n)

public static int getSum2(int num) {
	int total = num * (num + 1) / 2;
	return total;
}

• 반복문이 없고, 입력 값에 따라 알고리즘의 실행 횟수가 달라지지 않는다.
• 시간 복잡도 : O(1)

시간 복잡도 측면에서 아래의 알고리즘이 더 우수하다고 볼 수 있겠다!

오... 뭔가 굉장히 유식하게 알고리즘을 평가할 수 있게 되었다. 🤓