코드프레소 백엔드 개발자 양성 과정
점근 표기법
알고리즘이 작업을 완수하는 데까지 시간이 얼마나 소요되는지 표현하기 위한 척도가 있다. 바로 점근 표기법이라는 것이다. 수학에서는 함수의 증감 추세를 나타내기 위해 쓰이며, 전산과학에서는 알고리즘의 계산 복잡성, 즉 시간적 효율성을 따지기 위해 이용된다.
점근 표기법(asymptotic notation)이란?
알고리즘의 작업 처리 속도는 물론 컴퓨터의 연산력, 개발 언어, 컴파일러의 성능 따위에 영향을 받기 마련이다. 이런 변수를 고정해두고 동일한 환경에서 서로 다른 알고리즘을 실행한다고 하였을 때에만 비로소 효율성을 비교할 수 있다. 이때 이를 나타내는 방법이 점근 표기법이며, 관건이 되는 요소는 두 가지가 있다.
- 입력값의 크기에 따라 알고리즘이 실행되는 데에 경과되는 시간
- 입력값의 크기에 따라 복잡도 함수가 커지는 정도 (실행 시간의 성장률)
예시를 보며 무슨 뜻인지 알아본다. 알고리즘 ㄱ의 복잡도 함수는 n² + 2n + 3이고 알고리즘 ㄴ의 함수는 100n + 3이라고 하자. 그렇다면 입력값 n의 크기가 10일 때, 함수 ㄱ의 복잡도는 123, 함수 ㄴ의 복잡도는 1,003이 된다.
여기까지가 위에서 다룬 첫 번째 요소이다. 입력 크기가 10일 때, 단순히 알고리즘이 실행되는 데에 경과되는 시간만 본다면 함수 ㄱ이 빠르고 효율적, 함수 ㄴ이 느리고 비효율적이라고 잠정적으로나마 결론지을 수 있다.
하지만 두 번째 요소인 실행 시간의 성장률도 고려해야 한다. 이번에는 자료의 양이 늘어날 수록 복잡도가 얼마의 폭으로 증가하는지를 본다. 입력값 n의 크기가 1,000,000이라고 하자. 함수 ㄴ의 복잡도는 100,000,003에 그치는 반면, 함수 ㄱ의 복잡도는 기하급수적으로 늘어 1,000,002,000,003까지 치솟음을 볼 수 있다.
최종적으로 성능을 비교할 때, 우리는 함수 ㄴ이 함수 ㄱ보다 만 배 더 효율적이라고 표현하지 10,000.0197 배 더 효율적이라고 표현하지 않는다. 이것이 점근 표기법의 핵심이다. 직관적이고 대략적으로 효율성을 나타내기 위해 점근 표기법에서는 n² + 2n + 3과 100n + 3에서 불필요한 계수와 항을 무시하고 최고차항인 n²과 n만으로 비교하는 것이다.
달리 말하면, 계산 복잡도 함수의 최고차항의 차수가 낮을수록 처리하는 데이터의 양이 많아져도 효율적으로 작동하는 알고리즘이라고 할 수 있겠다. 반대로 최고차항의 차수가 높다면 더 비효율적이기 쉬운 알고리즘이다.
대문자 O 표기법 (Big O notation)
점근 표기법의 일종이며 가장 대표적으로 사용되는 대문자 O 표기법은 ‘점근 상한(asymptotic upper bound)’이라고도 한다. 이는 알고리즘이 작업을 수행할 때 소요될 수 있는 시간의 상한선을 뜻한다. 한마디로, 특정 알고리즘을 이용했을 때 발생할 수 있는 최악의 경우이다.
예를 들어, 주어진 숫자를 오름차순으로 정렬하는 알고리즘이 있다고 하자. 데이터가 비교적 정렬되어 주어지는 경우도 있고 큰 수와 작은 수가 완전히 뒤죽박죽으로 주어져 여러 차례 재정렬을 거듭해야만 하는 경우도 있기 마련이다. 자료의 양은 같아도 숫자를 움직여야 하는 횟수가 가장 많은 경우를 성능에 있어 ‘최악의 경우’라고 할 수 있으며, 이때의 효율성은 점근 상한 혹은 대문자 O 표기법으로 나타낸다.
그러므로 대문자 O의 값이 크면 클수록 효율의 최저점이 낮고 최대 작업 처리 시간이 길어진다. 하지만 역으로 매 상황이 ‘최악의 경우’일 리는 없으므로 알고리즘이 항상 딱 대문자 O의 값 만큼 비효율적이리란 보장은 없다 (위에서와 같이 데이터가 처리하기 수월한 형태로 주어진 경우).
이상으로 대문자 O 표기법에 대해 간단히 알아보았다.
