[Algorithm] 알고리즘 성능분석 방법

두번째로 알고리즘의 성능 분석 방법에 대해서 정리한다. 

성능 분석 방법이 필요한 이유는 우리가 자료를 처리할 때 단순이 잘 돌아만 가는것을 원하는게 아니라 어떠한 상황에서도 우월한 성능을 내기를 원하기 때문이다.

▶알고리즘을 평가하는 두가지 요소

시간 복잡도(Time complexity) : 얼마나 빠른가

공간 복잡도(space complexity) : 얼마나 메모리를 적게 사용하는가

알고리즘을 평가하는 요소로는 두가지가 있다. 하지만 사실 메모리를 작게 사용 한다는것도 시간에 관여를 한다. (CPU 사용에 영향을 끼치기 때문이다.) 따라서 일반적으로는 메모리 보단 시간에 좀더 관심을 두며, 중요한 요소라고 판단한다.

▶성능을 평가하는 방법

그럼 성능은 어떻게 평가를 할까?

위의 표를 보면 2개의 알고리즘 A, B 가 있다. 이 두개의 A, B를 비교해 보자~~~

위의 표만 보면 기준을 두가지로 나눌수 있다. 즉 데이터가 n 보다 작을때와 클때의 두가지로 나눌 수 있을 것이다. 

즉 데이터가 n 보다 작을 떄는 B 알고리즘이 성능이 좋고, 데이터의 수가 n 보다 클 때에는 A 알고리즘이 좋다는것을 판단 할 수 있을 것이다. 

그럼 두개의 알고리즘 중에 무엇이 좋다고 할 수 있을까??

정답은 A 알고리즘 이다. 왜 그럴까?

우리는 현재 자료구조를 공부 하기 위해서 이 이야기를 하고있다. 즉 얼마 되지도 않는 적은 양의 데이터를 중심으로 이야기 하겠다는 것이 아니다. 우리가 원하는 것은 엄청난 데이터 수 에서도 최상의 성능을 가지는 알고리즘이 필요한 것이다.

다시한번 위의 표를 보자, y축을 보면 연산 횟수 T(n)이라는 것을 볼 수 있다. 위의 표를 정확이 이해 했다면 하나의 알고리즘의 데이터 연산 횟수는 T(n)으로 나타낼 수가 있다는 것을 알 수 있다.

다음 연산을 살펴 보자

위의 식은 순차 검색 알고리짐이 된다. 위의 식에서 가장 중요한 연산을 찾아 보자.

지금 위의 알고리즘에서 사용된 연산은 총 3가지 이다. <, ++, == 의 세가지 연산이므로 무엇을 가장 중요하다고 할 수 있을까? 

현재 우리가 보고 있는 알고이즘에서 연산 작업을 하는것은 for문이다. 그래서  for문에 있는 ++ 이나 < 가 더 중요해 보일수 있다.

하지만 위의 알고리즘의 역활은 검색 기능이다. 따라서 가장 중요한 검색(비교)를 하는 == 연산이 가장 중요하다고 할 수 있다.

위의 연산에서의 최악의 경우는 언제일까? 아마도 자료를 찾지 못해서 for문 끝까지 검색을을 하는것이 아닐까?

이를 T(n)으로 나타내면 다음과 같다.

 

자 우리가 이 파트에서 다룰 내용은 알고리즘의 성능 분석이였다. 와 그럼 알고리즘의 성능은 T(n)으로 표연하는 구나 하고 넘어 갈 수있다. 하지만 그래서는 안된다.

말이 너무 길어 졌지만 이제부터 진짜 성능을 나타 내는 방법에 대해 이야기 할 것이다.

▶빅-오 표기법(Big oh Notation)

빅 오 표기법이란, T(n)의 식에서 실질적인 영향을 끼치는 부분을 가리킨다.

다음 식을 보자 

위의 과정을 보면 가장 최고차랑이 높은 식을 가리켜 빅오의 값으로 얻고 있다. 그렇다면 왜 남어지는 영향력이없다고 생각할까?

여기서 다시 초기 부분을 생각해야 한다. 우리가 알고리즘의 성능을 판단 할 때에는 항상 극한의 상황을 고려한다고 했다. 다음 표를 보자

위의 표에서는 각각의 연산의 영향력 나타낼 수 있다 보면 데이터량(n)이 커질수록 최고차항의 영향력이 커지는것을 알 수있다. 따라서 성능을 평가 할 떄에는 항상 가장 높은 차항의 값을 데이터화 하여 개선 방안을 찾아 내어야 한다.

그럼 우리가 알고리즘을 만들떄 어떠한 알고리즘이 좋다고 할 수 있을까?

자 이제 위의 두 식을 보고 알고리즘의 성능이 어떤 그래프를 그리는것이 좋다고 할 것인가? 

이떄 왼쪽거라고 하신분은 다시한번 공부를 해야 할 것이다. 우리는 항상 데이터가 무수히 많을때를 생각하기 때문에 오른쪽 같은 로그 그래프를 가지는 알고리즘을 좋은 알고리즘이라고 이야기 한다.

지금까지 간단하게 알고리즘의 성능 분석 방법에 대해 이야기 하였다. 다음에는 좀더 자세하고 실 구현적인 방법에 대하여 설명해야겠다.

※이미지는 윤성우의 열혈 자료구조에 ppt에서 가져온것입니다.