1.5알고리즘 성능 분석

이어서 알고리즘 성능 분석에 쓰이는 빅오(Big-O)라는 개념에 대해 알아봅시다.

■ 빅오

일반적으로 알고리즘 성능 분석의 기준은 실행되는 데 걸리는 초나 분 같은 절대적인 시간이 아니라 ‘데이터 크기가 커지면 분기문을 몇 번 더 실행해야 하는가?’ 같은 상대적인 연산 횟수입니다. 빅오는 데이터 개수가 증가하면 연산 횟수가 어떤 경향을 나타내는지 보여 주는 개념입니다. 연산 횟수를 계산하는 완벽한 식이 아니라 연산 횟수의 증가 추세만 표현합니다.

예를 들어 연산 횟수를 구하는 식이 다음과 같다고 가정합니다.

식의 증가 추세는 n² 그래프와 같을 것입니다. 이때 n²을 이 알고리즘의 빅오라고 하고 O(n²)이라고 표현합니다.