알아 보기

 

자, 우리는 이렇게 1부터 n까지의 합을 구하는 알고리즘을 두 개 만들어 보았습니다. 여러분은 앞에서 살펴본 두 알고리즘 중 어떤 알고리즘을 사용하고 싶나요?

당연히 두 번째 방법이 더 좋은 방법이라 여길 것입니다. 왜냐하면 첫 번째 방법은 입력 값 n이 커질수록 덧셈을 훨씬 더 많이 반복해야 하지만, 두 번째 방법은 n 값의 크기와 관계없이 덧셈, 곱셈, 나눗셈을 각각 한 번씩만 하면 답을 얻을 수 있기 때문입니다.

 

그림 1-4 1부터 n까지 연속한 숫자의 합을 구하는 두 가지 방법

 

이렇게 주어진 문제를 푸는 여러 가지 방법 중 어떤 방법이 더 좋은 것인지 판단할 때 필요한 것이 ‘알고리즘 분석’입니다.

알고리즘 분석은 알고리즘 작성 못지않게 중요하지만, 안타깝게도 복잡한 수학 이론이 필요한 경우가 많습니다. 하지만 이 책에서는 되도록 수학 이론이나 증명을 생략하고 개념만 설명하려고 합니다.