알고리즘과 자료구조는 서로 다른 하나의 과목임에 불구하고 밀접한 연관이 있다.
자료구조를 공부하기전 알고리즘의 성능분석을 알아보고 자료구조를 사용할 때 어떤 알고리즘의 성능이 좋고 비용이 낮은지 살펴보자.
알고리즘의 성능분석에는 2가지 측면이 있다.
1. 시간 복잡도 : 속도에 해당하는 알고리즘의 수행시간 분석결과
2. 공간 복잡도 : 메모리 사용량에 대한 분석결과
일반적으로 알고리즘을 평가할 떄는 메모리의 사용량보다 실행속도에 초점을 둔다.
그렇다면 어떻게 속도를 측정할까?
알고리즘의 수행속도를 평가할 떄는 연산의 횟수와 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.
함수를 잘 구성해 놓으면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 파악함으로써 속도를 측정해 볼 수 있다.
알고리즘의 시간 복잡도를 계산하기 위해서는 코드에서 핵심이 되는 연산이 무엇인지 잘 판단해야한다. 그러나 쉬운 일은 아니다.
또한 알고리즘을 평가하는데 있어서 최선의 경우보다는 최악의 경우를 기준으로 성능을 평가한다. 그 이유는 어떠한 알고리즘이라도 최선의 경우만 나오기 힘들고 최악의 경우가 나올 확률도 배제할 수 없기 때문이다. 예측불가능 한 경우에는 최악의 경우를 선택하는 것이 계산하기도 편리하고 데이터의 수가 굉장이 많다면 최선보다는 최악을 선택하는 것이 최선과 최선의 성능 범주를 아우를 수 있다.
빅-오 표현법(Big-Oh Notation)
사실 데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 구하는 것은 쉽지않다. 이를 위해 어느정도의 오차는 무시하고 데이터 수의 증가에 따른 연산횟수의 증가 형태 또는 증가율의 상한선을 표현한 것이 빅-오 표현법이다.
댓글 없음:
댓글 쓰기