빅 오 표기법(Big-O Notation)

Dion·2020년 3월 10일
3

알고리즘

목록 보기
3/7

참고: 칸 아카데미 알고리즘 > 점근적 표기법

표기법이란?

대개의 경우 알고리즘의 실행 시간은 컴퓨터가 알고리즘을 실행하는 속도에 의존합니다.

이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.

하지만 우리는 이 시간을 대략적으로 추측할 수 있는 방법이 필요합니다. 그래서 표기법이 등장했습니다.


그럼 이 표기법은 어떻게 계산할까요? 수학적으로 생각한다면, 요소가 n이 증가하면 그에 비례해서 시간이 일정하게 증가하는 경우 n만큼 걸린다고 볼 수 있을 것입니다. 그리고, 2배로 비례해서 증가한다면 2n이 되겠죠. 또, 제곱으로 비례해서 증가한다면 n2 이라고 볼 수 있습니다.

이렇게 입력값의 크기에 따라 알고리즘이 얼마나 실행속도가 증가하는지 알아보는 것을 실행 시간의 성장률(rate of growth)이라고 부릅니다. 6n2+100n+300 이라는 성장률에 대한 함수가 있을 때, 우리는 이를 간소화해서 보는 편이 더 좋을 것입니다. 실제로 n이 증가함에 따라 6n2에 비해서 100n+300의 비중은 그리 크지 않게됩니다.


따라서 우리는 약속을 합니다. 계수인 6, 그리고 나머지 항목인 100n+300을 제외하고 실질적으로 알고리즘의 실행속도에 가장 큰 영향을 미치는 부분인 n2만으로도 충분하다는 것이죠.

이렇게 중요하지 않은 항과, 상수 계수를 제거하면 알고리즘을 이해하는데 방해되는 불필요한 부분을 생각하지 않을 수 있어서 알고리즘에서 중요한 부분인 성쟝률에 집중할 수 있습니다.

이렇게 중요하지 않은 항과, 상수 계수를 제거한 표기법을 점근적 표기법(asymptotic notation)이라고 합니다.

왜 표기법을 사용할까?

표기법을 사용하는 이유는 알고리즘의 효율성을 나타내는 지표이기 때문입니다.

또, 다른 개발자와 알고리즘에 대하여 얘기할 때, 표기법을 이용하여 소통하는 편이 더 원활하기 때문입니다.

빅 오 표기법이란?

알고리즘을 실행하였을 때, 최악의 경우를 의미합니다. 가장 보편적으로 사용하는 표기법입니다. 한계를 위에다만 두는 것이지요.

이를 시간(또는 공간)의 상한선이라고도 합니다.

정확한 뉘앙스는 "실행 시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다." 라는 의미입니다.

쉽게 설명하면, "제일 오래걸리면 이 정도 걸릴 것이다." 라는 의미라고도 볼 수 있습니다.

이는 대개의 알고리즘은 시간에 대해서 얘기하는 경향이 있기 때문입니다. (항상 알고리즘은 시간과 공간의 적절한 조화가 중요합니다.)

다른 표기법에는 무엇이 있을까요?

  • 빅 오메가 표기법
    • 가장 최선의 경우를 의미합니다.
  • 빅 세타 표기법
    • 평균적인 상황의 경우를 의미합니다. 빅 오와 빅 오메가의 공통부분입니다. 세타 표기법으로 표기할 수 없는 경우도 존재합니다.
  • 이를 제외한 나머지 표기법들도 존재하나, 거의 쓰이지 않습니다.

왜 빅 오 표기법이 다른 표기법 보다 많이 쓰일까요?

대부분의 경우 우리의 관심이 가장 최악의 경우에 어떻게 될 것인지에 쏠려있기 때문입니다.

아무리 linear search가 최선의 경우 1의 속도를 가진다고 해도, 최악의 경우 n의 속도가 걸리기 때문에 사용하지 않는 것과 같은 이유라고 보면 될 것 같습니다.

profile
코드리뷰와 고양이를 좋아하는 개발자입니다. 좋은 글을 위한 비판은 언제든 환영합니다.

4개의 댓글

comment-user-thumbnail
2020년 3월 10일

왜 빅오표기법을 사용할까? 부분에 '원할' 오타 있습니다ㅎㅎㅎ 글 잘 읽고가요!

1개의 답글
comment-user-thumbnail
2020년 3월 10일

공간 복잡도에서 '공간'은 메모리를 의미하는건가요??

1개의 답글