알고리즘의 성능 분석 방법

저번 시간에는 자료 구조와 알고리즘의 차이에 대해 공부해봤습니다. 저번에 배운 자료 구조와 알고리즘의 차이를 완벽하게 이해 하셨나요? 조금이라도 헷갈린다면 아래 글을 클릭하여 다시 한 번 읽어 보시는 걸 추천드립니다. 다 이해가 되셨다면 이번 시간에는 알고리즘의 성능을 분석하는 방법에 대해 알아보도록 하겠습니다. 

 

알고리즘 성능 분석의 필요성

요즘 컴퓨터는 엄청난 계산 속도와 방대한 메모리를 자랑합니다. 그렇다고 해서 프로그램의 계산 시간을 줄이고 메모리를 효과적으로 사용하는 것이 더 이상 고민할 필요가 없는 것일까요? 당연히 그렇지 않겠죠. 요즘에도 여전히 프로그램의 효율성은 중요합니다. 효율성이 중요한 이유는 다음과 같습니다.

• 첫 번째 최근 프로그램의 규모가 엄청나게 크기 때문에 알고리즘의 효율성이 중요하다.
• 두 번째 사용자들은 여전히 빠른 프로그램을 선호하기 때문에 경쟁사의 프로그램보다 빨라야 한다.

 

 

알고리즘 성능 분석 방법

프로그램의 효율을 측정하는 방법은 알고리즘을 작성하여 실제 컴퓨터상에서 실행시킨 다음, 그 실행 시간을 측정하는 것입니다. 대단히 효과적인 방법으로 알려져 있다. 그러나 몇 가지 문제점이 있다. 알고리즘이 복잡한 경우 구현하는 것이 큰 부담이 될 수 있다. 이 방법을 사용하려면 똑같은 하드웨어 조건을 가진 컴퓨터 상에서 실행해야 하기 때문에 결과가 달라질 수 있다. 또한 실험에 사용했던 데이터가 아닌 다른 데이터에 대해서는 전혀 다른 결과가 나올 수 있다. 즉 실험되지 않은 입력에 대해서는 실행 시간을 주장할 수 없다.

 

알고리즘의 복잡도 분석 방법

직접 구현하지 않고 알고리즘의 효율성을 따져보는 방법이 알고리즘의 복잡도 분석이다. 복잡도 분석은 구현하지 않고도 모든 입력을 고려하는 방법이고 실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다. 알고리즘의 실행 시간 분석을 시간 복잡도라고 하고 알고리즘이 사용하는 기억 공간 분석을 공간 복잡도라고 한다. 흔히 알고리즘의 복잡도를 이야기할 때는 시간 복잡도를 말한다. 시간 복잡도는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 이루고 있는 연산들이 몇 번 실행되는지를 숫자로 표시하는 것이기 때문에 헷갈리지 않게 주의해야한다.