알고리즘 분석

알고리즘 분석¶

알고리즘 분석은 알고리즘의 성능을 연구하는 컴퓨터 과학의 한 분야로, 특히 실행시간과 필요공간에 대해 연구한다. 더 많은 정보를 보려면 http://en.wikipedia.org/wiki/Analysis_of_algorithms 를 참고하자.

알고리즘 분석의 실질적인 목표는 디자인을 결정하기 위해서 여러 가지 다른 알고리즘들의 성능을 예측하는 것이다.

2008년 미국의 대선 캠페인 기간에 구글을 방문했을 때 버락 오바마 후보는 즉흥적인 분석을 해보라는 요청을 받았다. 에릭 슈미트 최고경영자는 그에게 농담 삼아 '100만 개의 32비트 정수들을 정렬하는 가장 효율적인 방법은 무엇이냐'고 물었다. 분명히 오바마는 누구에게 귀띔을 받았을 것이다. 재빠르게 '버블 정렬 알고리즘은 아닌 것 같군요'라고 했으니 말이다. 관련 영상은 다음 링크에 있다. http://www.youtube.com/watch?v=k4RRi_ntQc8

오바마의 말은 사실이다. 버블 정렬은 개념적으로는 단순하지만 큰 데이터세트를 대상으로 한다면 느릴 수밖에 없다. 아마 슈미트 최고경영자가 찾던 답은 '기수 정렬'이었을 것이다.http://en.wikipedia.org/wiki/Radix_sort
https://www.youtube.com/watch?v=ibtN8rY7V5k 기수정렬 알고리즘 유튜브 영상

알고리즘 분석은 알고리즘들 간의 의미 있는 비교를 목표로 하지만, 몇 가지 문제점이 있다.

• 알고리즘의 상대적인 성능은 하드웨어의 특성에 달려 있으므로, 어떤 알고리즘이 기계 A에서 빠르다면, 기계 B에서는 다른 알고리즘이 빠를 수 있다. 이러한 문제를 해결하기 위해서는 일반적으로 '기계 모델'을 지정하고, 주어진 모델의 조건 아래 조사하고자 하는 알고리즘에서 필요로 하는 단계의 수를 분석한다.

• 상대적인 성능은 데이터세트의 세부 내용에 따라 달라질 수 잇다. 이를테면 어떤 정렬 알고리즘들은 데이터가 미리 부분적으로 정렬되어 있을 때 더 빠르게 실행된다. 반면에 어떤 알고리즘들은 이런 경우 더 느리다.ㅏ 이 같은 문제를 예방하기 위해서 흔히 쓰는 방법은 최악의 시나리오를 분석하는 것이다. 때로는 평균을 내는 성능 분석도 유용하지만 그것이 더 어려운 방법이기도 하고, 평균낼 케이스들이 불분명한 경우도 있다.

• 상대적인 성능은 또한 문제의 크기에 따라 다르기도 하다. 작은 리스트를 대상으로 실행했을 때 빠른 알고리즘이, 긴 리스트에 대해서는 느릴수도 있다. 이러한 문제에 대한 일반적인 해결책은 실행시간(또는 연산 수)을 문제 크기에 대한 함수로 표현한 다음, 문제 크기가 증가함에 따라서 함수들을 점근적으로 비교하는 것이다.

이러한 방식의 비교는 알고리즘을 단순하게 분류하는 데 적합하다는 장점이 있다. 예를 들어서 내가 알고리즘 A의 실행시간이 입력 n의 크기에 비례하며, 알고리즘 B가 n^2에 비례한다는 사실을 알고 있다면, n이 클 때는 B보다 A가 빠르리라고 예상이 가능하다.

이 같은 분석법에는 몇몇 주의사항이 있으며 이에 대해서는 나중에 다루겠다.

이미지 출처 : https://m.post.naver.com/viewer/postView.nhn?volumeNo=13362220&memberNo=1464463&vType=VERTICAL

내용 출처 : 복잡계와 데이터 과학