Big-O 표기법

칸아카데미에서 점근적 표기법 강의를 보고 정리했다. 

Big-O 표기법

알고리즘이 얼마나 오래 걸리는지를 표현하는 대표적인 방법 중 하나이다.

알고리즘의 실행 시간은 컴퓨터가 코드를 실행하는 속도에 의존한다.

그리고 이 속도는 컴퓨터 자체의 성능, 사용된 언어, 컴파일러 등에 의존적이다.

따라서 단순히 "이 알고리즘은 30분 쯤 걸려요" 같은 말은 할 수가 없는 것이다.

 

입력값의 크기를 n이라고 할 때, 알고리즘을 실행하기 위한 연산의 횟수를 n에 대한 식, 즉 일종의 함수로 표현할 수 있다.

알고리즘의 실행 시간을 입력값의 크기에 대한 함숫값으로 생각할 수 있는 것이다.

이 때 입력값의 크기에 따라 함숫값이 얼마나 빨리 커지는지를 실행시간의 성장률이라고 부른다.

 

성장률을 파악할 때, 계수와 상수는 불필요하다. n이 커질수록 n의 차수가 함숫값에 미치는 영향이 압도적으로 크기 때문이다.

상수, 계수, 낮은 차수의 항 같은 중요하지 않은 부분을 제거하여 표현하는 것을 점근적 표기법(asymptotic notation)이라고 한다.

이 점근적 표기법에는 big-o, big-세타, big-오메가 표기법이 있다.

예를 들어 입력값, 크기가 n인 알고리즘이 6n^2 + 100n + 3006이라는 기계 명령을 받는다고 가정하자.

점근적 표기법에서는 여기서 가장 차수가 높은 6n^2가 주 관심사이다.

 

참고: "점근" 이란?

점근이란 어떤 함수나 값이 다른 값에 무한히 다가가는 상태를 뜻한다. 그리고 이 ‘다가가는 값’을 차원에 따라 선이나 점의 형태로 표현하는데, 일차원 상에서 점으로 표현된 것이 점근점이다. 사실 점근점보다는 점근선의 형태로 더 자주 쓰인다. 예를 들어 y=1/x + 1라는 함수가 있다. 이때 x가 0보다 큰 상태에서, x값에 따라 y값은 1에 무한히 가까워진다. 이때 x축과 평행한 (0,1)을 지나는 직선을 그으면 x값이 무한대로 감에 따라 함수의 그래프는 이 직선에 가까워진다. 이 경우 이 직선을 점근선이라고 부른다. 출처: https://www.scienceall.com/%EC%A0%90%EA%B7%BC%EC%A0%90asymptotic-point/

(1) big-Θ

어떤 함수 f(n)에 대하여 실행시간이 Θ(f(n))이라는 것은 n값이 충분히 커지면 실행 시간이 k1 * f(n)과 k2 * f(n) 사이에 있게 된다는 뜻이다. 즉, 실행 시간에 대해 점근적으로 근접한 한계값이 있다는 뜻이다.

"점근적으로"라는 말을 쓰는 이유는 큰 값의 n에 대해서만 적용되기 때문이다.

"근접한 한계값"이라는 말은 위, 아래로 상수값 내에서 실행 시간을 좁힐 수 있다는 뜻이다.

 

(2) big-O

big-O 표기법은 "실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다"는 의미이다.

점근적 한계를 위아래로 둔 것이 아니라 위에만 둔 것이다.

예를 들어, 최악의 경우에 이진 검색의 실행 시간은 Θ(log 2(n))이지만, 모든 경우에 그러하다고는 할 수 없다.

n이 백만개라도 첫 번째 추측에 찾을 수 있기 때문이다.

따라서 모든 경우를 포괄하는 일반적 표현으로는, 이진 검색은 O(log2(​n))이라고 할 수 있다.

 

(3) big-Ω

점근적 한계를 아래에만 둔 것이다. 예를 들어, 이진 검색의 실행 시간은 Ω(1)이라고 할 수 있다. 정확한 표현은 아니지만, 어쨌든 항상 옳다. 어떤 경우에든 무조건 상수 시간 이상이 걸리기 때문이다.

 

---

참고: 칸아카데미 https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation