5입력 크기와 계산 횟수

 

알고리즘에는 입력이 필요한데 입력 크기가 알고리즘의 수행 성능에 영향을 미칠 때가 많습니다. 입력 크기가 커지면 당연히 알고리즘의 계산도 복잡해지겠죠? 1부터 n까지의 합을 구하는 문제를 통해서 입력 크기와 계산 횟수의 관계를 생각해 봅시다.

1부터 n까지의 합을 구하는 문제에서는 n의 크기가 바로 입력 크기입니다. 첫 번째 알고리즘, 즉 s에 0을 넣고 차례로 1, 2, 3 … 을 더해서 합계를 구하는 프로그램의 경우 10까지의 합을 구하려면 덧셈을 열 번, 100까지의 합을 구하려면 덧셈을 백 번 해야 합니다. 하지만 두 번째 알고리즘은 어떤가요? 입력 크기 n이 아무리 큰 수라도 덧셈을 한 번, 곱셈을 한 번, 나눗셈을 한 번 하면 결과를 얻을 수 있습니다.

계산하는 데 필요한 사칙연산의 횟수는 다음과 같습니다.

 

• 첫 번째 알고리즘(프로그램 1-1): 덧셈 n번

• 두 번째 알고리즘(프로그램 1-2): 덧셈, 곱셈, 나눗셈 각 한 번(총 세 번)

 

입력 크기 n이 작을 때는 두 가지 방법이 큰 차이가 나지 않습니다. 하지만 n이 커지면 커질수록 엄청난 차이가 납니다. n = 1000이 되면 첫 번째 알고리즘은 덧셈을 천 번 해야 하므로 세 번만 계산해도 되는 두 번째 알고리즘과 엄청나게 차이가 납니다.

보통 컴퓨터를 이용해서 계산할 때는 입력 크기 n이 매우 큰 경우가 많습니다. 알고리즘 분석에서는 입력 크기가 매우 큰 n에 대해서 따져 보는 것이 중요합니다. 예를 들어 우리나라 전 국민의 평균 나이를 계산하는 문제라고 하면 입력 크기 n은 우리나라 전 국민에 해당하는 50,000,000이 넘는 수입니다.