6대문자 O 표기법: 계산 복잡도 표현

 

어떤 알고리즘이 문제를 풀기 위해 해야 하는 계산이 얼마나 복잡한지 나타낸 정도를 ‘계산 복잡도(complexity)’라고 합니다. 계산 복잡도를 표현하는 방법에는 여러 가지가 있는데, 그 중 대문자 O 표기법을 가장 많이 사용합니다(대문자 O표기법은 ‘빅 오’ 표기법이라고도 부릅니다).

대문자 O 표기법의 정확한 정의와 설명은 일단 생략하고, 앞에서 살펴본 예제 프로그램의 계산 복잡도를 대문자 O로 표기하는 방법부터 설명하겠습니다.

첫 번째 알고리즘은 입력 크기 n에 대해 사칙 연산(덧셈)을 n번 해야 합니다. 이때 이 알고리즘의 계산 복잡도를 O(n)이라고 표현합니다. 필요한 계산 횟수가 입력 크기에 ‘정비례’할 때는 O(n)이라고 표현합니다.

입력 크기 n에 따라 덧셈을 두 번씩 하는 알고리즘이 있다면 어떨까요? 얼핏 생각하면 O(2n)으로 표현할 것 같지만, 그렇지 않습니다. 이때도 마찬가지로 그냥 O(n)으로 표현합니다. 대문자 O 표기법은 알고리즘에서 필요한 계산 횟수를 정확한 숫자로 표현하는 것이 아니라 입력 크기와의 관계로 표현하기 때문입니다. 예를 들어 n이 10에서 20으로 ‘2배’가 될 때 2n 역시 20에서 40으로 ‘2배’가 됩니다. 이처럼 필요한 계산 횟수가 입력 크기 n과 ‘정비례’하면 모두 O(n)으로 표기합니다.

두 번째 알고리즘은 입력 크기 n과 무관하게 사칙연산을 세 번해야 합니다. 이때 알고리즘의 계산 복잡도는 O(1)로 표현합니다. 왜 O(3)이 아니냐고요? 앞에서 O(2n)을 O(n)으로 표현하는 것과 같은 원리입니다. 입력 크기 n과 필요한 계산의 횟수가 무관하다면, 즉 입력 크기가 커져도 계산 시간이 더 늘어나지 않는다면 모두 O(1)로 표기합니다.