3. 알고리즘 분석

어떤 응용프로그램인지에 따라 어떤 구현체를 사용하여 데이터를 처리하는게 좋은지 

알 수 있는 방법중 한가지 방법은 두 구현체를 모두 구현하여 비교해보는 것이다.

 

이 방법에는 몇 가지 문제점이있고 다음과 같다.

 

- 알고리즘 비교시 사전에 모두 구현하여 비교해봐야한다 (비용 상승)

- 경과는 사용 컴퓨터의 성능에 의전한다.

- 결과는 문제 크기나 입력으로 사용하는 데이터에 의존하기도 한다.

 

알고리즘 분석을 사용하면 이런 문제들을 해결할 수 있다.

하지만 몇가지를 가정해야하는데 그 는 아래와 같다.

 

1. 하드웨어에 세부사항을 다루지 않기에 보통 알고리즘을 이루는 기본 사칙 연산등의

기본연산을 식별하며 이 연산 수를 센다.

 

2. 입력데이터의 세부사항을 다루지 않기위해 평균 성능 분석을 하며 가능하지 않을때는

최악의 시나리오로 분석한다.

 

3. 알고리즘이 작은 문제에서는 최상의 성능을 보이지만 큰 문제에 대해서는 다른 알고리즘이

더 좋을 수 있다는것을 배제하면 안된다.

 

이러한 종류의 분석은 간단한 알고리즘 분류에 적합하며

알고리즘 A의 실행시간이 입력 n의 크기에 비례하고 알고리즘 B는 n제곱에 비례하는 경향이 있다면 

적어도 n의 값이 클때는 A가 B보다 빠르다고 기대한다라는 것이다.

 

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

 

- 상수시간

실행시간이 입력 크기에 의존하지 않으면 알고리즘은 상수 시간을 따른다고 하며 예를 들면

n개의 배열에서 브래킷 연산( [ ] )을 사용하여 요소 중 하나에 접근할 때 이 연산은 배열의 크기와 관계없이

같은 수의 동작을 수행한다.

 

즉 입력값 n 에 상관없이 알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.

 

 

- 선형 

예로 어떤 배열에 특정 요소를 더한다 한다면 n개의 요소에 접근하여 n-1번 더하기 연산을 해야하고

연산 통횟수는 2n-1 이고 n에 비례한다.

 

즉 실행시간이 입력크기에 비례하여 증가함을 나타낸다.

 

- 이차 

작업을 수행하는데 걸리는 단계의 수가 n²이다.