4알고리즘 분석

 

잠깐만 봐도 첫 번째 알고리즘보다 두 번째 알고리즘이 더 효율적이라는 것을 알 수 있습니다. 그러면 각각의 계산 복잡도는 어떻게 될까요?

모든 경우를 비교한 첫 번째 알고리즘(프로그램 18-1)은 문제 3 동명이인 찾기와 비슷한 구조입니다. 모든 이름을 일일이 비교하면서 찾는 방식으로 계산 복잡도는 O(n²)입니다.

반면, 리스트를 한 번 탐색하면서 최대 수익을 계산한 두 번째 알고리즘(프로그램 18-2)은 문제 2 최댓값 찾기와 비슷한 구조로 계산 복잡도는 O(n)입니다.

입력 크기가 커질수록, 즉 더 많은 날의 주가가 입력으로 주어질수록 두 번째 알고리즘이 첫 번째 알고리즘보다 결과를 훨씬 빨리 낼 거라고 충분히 예상할 수 있습니다.

그런데 실제로는 얼마나 차이가 날까요? 궁금한 독자들을 위해 최대 수익 문제를 두 가지 다른 방법으로 풀 때 걸리는 시간을 비교하는 프로그램을 만들어 보았습니다.