analysis of algorithm(알고리즘 분석)

어떤 응용 프로그램에 어느 클래스가 더 좋을지 결정하는 한 가지 방법은 둘 다 시도해 보고 각각 얼마나 걸리는지 알아보는 것이다. 이러한 접근법을 프로파일링(profiling)이라고 하는데, 여기에는 몇 가지 문제점이 있다. 

1. 알고리즘을 비교하려면 사전에 그것을 모두 구현해봐야 한다.
2. 결과는 사용하는 컴퓨터의 성능에 의존한다. 한 알고리즘이 어떤 컴퓨터에서는 더 좋을 수 있지만, 다른 알고리즘은 다른 컴퓨터에서 더 좋을 수도 있다.
3. 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다.

알고리즘 분석(analysis of algorithm)을 사용하여 이러한 문제점을 해결할 수 있다. 알고리즘 분석은 그것을 구현하지 않고도 알고리즘을 비교할 수 있게 한다. 하지만 몇 가지 가정을 해야만 한다.

1. 컴퓨터 하드웨어의 세부사항을 다루지 않기 위해 보통 알고리즘을 이루는 더하기와 곱하기, 숫자 비교 등의 기본 연산을 식별한다. 그리고 각 알고리즘에 필요한 연산 수를 센다.
2. 입력 데이터의 세부사항을 다루지 않으려면 가장 좋은 선택은 기대하는 입력 데이터에 대한 평균 성능을 분석하는 것이다. 이것이 가능하지 않을 때는 일반적인 대안으로 최악의 시나리오를 분석하기도 한다.
3. 마지막으로, 한 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에서는 다른 알고리즘이 더 좋을 수 있다는 가능성을 배제하면 안된다. 이때는 보통 큰 문제에 초점을 맞춘다. 작은 문제에서는 알고리즘의 차이가 크지 않지만, 큰 문제에서는 그 차이가 훨씬 거대해질 수 있기 때문이다.

이러한 종류의 분석은 간단한 알고리즘 분류에 적합하다. 예를 들어, 알고리즘 A의 실행시간이 입력 n의 크기에 비례하고 알고리즘 B는 n²에 비례하는 경향이 있다면 적어도 n의 값이 클 때는 A가 B보다 빠르다고 기대한다.

 

대부분 간단한 알고리즘은 다음 몇 가지 범주로 나뉜다.

• 상수 시간 : 실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간(constant time)을 따른다고 한다. 예를 들어, n개의 배열에서 브래킷 연산([ ])을 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계없이 같은 수의 동작을 수행한다.
• 선형 : 실행시간이 입력의 크기에 비례하면 알고리즘은 선형(linear)이라고 한다. 예를 들어, 배열에 있는 요소를 더한다면 n개 요소에 접근하여 n-1번 더하기 연산을 해야 한다. 연산(요소 접근과 더하기)의 총 횟수는 2n-1이고 n에 비례한다.
• 이차 : 실행시간이 n²에 비례하면 알고리즘은 이차(quadratic)라고 한다. 예를 들어, 리스트에 있는 어떤 요소가 두 번 이상 나타나는지 알고 싶다고 가정한다. 간단한 알고리즘은 각 요소를 다른 모든 요소와 비교하는 것이다. n개의 요소가 있고 각각 n-1개의 다른 요소와 비교하면 총 비교 횟수는 n²-n이 되어 n이 커지면서 n²에 비례하게 된다.