성능(Performance) 분석을 하는 이유
프로그램을 작성할 때 고려해야하는 사항이 많다. 사용자 편의성이 좋아야하며, 모듈성, 보안, 유지 관리 등이 중요하다. 이 뿐만 아니라 성능도 중요하다. 그렇다면 성능은 왜 중요한 것일까? 답은 간단하다. 성능이 좋아야 앞서 언급한 것들을 이룰 수 있다.
성능을 공부하는 이유 중 또 다른 하나는 재미있기 때문이다.
조금 더 실용적인 예를 들어보자. 만약 워드나 한글 같은 텍스트 에디터가 100페이지를 로드하는데 한시간이 걸린다면 어떨까? 동영상을 재생하기 위해 1시간이 걸린다면 어떨까? 이러한 경우 퍼포먼스, 즉 성능은 필수적이다.
성능 분석은 어떻게 할 수 있을까?
하나의 문제 혹은 태스크를 풀 수 있는 두 가지 알고리즘이 있다고 생각해 보자. 어느 것이 나은지 어떻게 판단할 수 있을까? 가장 기본적인 방법은 실행해 보면 된다. 각 알고리즘을 실행해서 실행 시간을 비교하면 된다. 그런데 여기에 약간의 변수가 존재한다. 입력 데이터에 따라 알고리즘의 성능이 바뀌는 경우가 있다. 또는 알고리즘을 실행하는 컴퓨터마다 성능이 다른 경우가 있다. 이 문제를 해결하기 위한 알고리즘 분석 방법이 점근적 분석(Asymptotic Analysis)이다.
점근적 분석 방법을 구체적으로 알아보자.
점근적 분석에서는 알고리즘을 입력 크기에 따라 성능을 평가한다. 실제로 실행 시간을 측정하지 않는다. 입력 크기가 커질 때 알고리즘이 걸리는 시간을 얼마나 되는지 계산한다.
예를 들어보자. 주어진 숫자 배열을 탐색한다고 생각하자.
탐색하는 방법으로 선형 탐색과 이진 탐색이 있다. 실제로 이진 탐색을 느린 컴퓨터에서 실행하면 입력 크기가 아주 클때 선형 탐색보다 좋은 성능을 나타낸다.선형 탐색은 입력 크기에 따라 선형으로 비례하고 이진 탐색은 로그 함수적으로 증가한다.
점근적 분석 방법은 항상 잘 작동하나?
점근적 분석 방법은 완벽하지 않다. 하지만 알고리즘을 분석하는 가능한 최고의 방법이다.
점근적 분석에서는 상수를 무시한다. 따라서 10n의 성능을 보이는 알고리즘과 100n의 성능을 가지는 알고리즘은 점근적으로 같다.
또한 점근적 분석에서는 입력 크기가 아주 클 때에 대해서만 이야기 한다. 하지만 실제로는 그만큼 큰 입력이 주어지지 않을 수 있다. 따라서 특정 상황에서는 점근적으로 느린 알고리즘이 좋은 성능을 내기도 한다.
'점근적'이라는 의미는 무엇일까?
수학적 분석에서 점근적 분석은 행동을 제한하는 것을 묘사하는 방법이다.
위의 식에서 n 이 아주 커질 때 n 제곱에 비하면 n은 비교조차 할 수 없을 정도로 작다. 따라서 위 식은 n 제곱에 점근적으로 다가간다.
$ x^{2} $
https://www.geeksforgeeks.org/analysis-of-algorithms-set-1-asymptotic-analysis/
댓글