3알고리즘 분석

 

최댓값 구하기 프로그램의 계산 복잡도(시간 복잡도)를 생각해 봅시다. 입력 크기가 n일 때, 즉 숫자 n개 중에서 최댓값을 구할 경우 자료 개수 n은 리스트 a의 크기인 len(a)로 쉽게 구할 수 있습니다.

그렇다면 최댓값을 구하는 데 컴퓨터가 해야 하는 가장 중요한 계산은 무엇일까요? 두 값 중 어느 것이 더 큰지를 판단하는 ‘비교’입니다. 프로그램 2-1에서는 for i in range(1, n): 반복문 안에 크기를 비교하는 판단 구문(if a[i] > max_v:)이 있어 자료 n개 중에서 최댓값을 찾으려면 비교를 n-1번 해야 합니다.

이때 계산 복잡도는 O(n-1)일까요? 정답은 O(n)입니다. 문제 1에서 설명한 것처럼 n이 굉장히 커질 때는 n번과 n-1번의 차이가 무의미하므로 간단히 O(n)으로 표현합니다.

계산 복잡도 O(n)의 가장 중요한 특징은 입력 크기와 계산 시간이 대체로 비례한다는 것입니다. 바꿔 말하면 숫자 10,000개 중 최댓값을 찾는 데 걸리는 시간이 10초였다면 20,000개를 입력할 때는 대략 20초가 걸릴 것으로 예상할 수 있다는 말입니다.