표기법이란?
대개의 경우 알고리즘의 실행 시간은 컴퓨터가 알고리즘을 실행하는 속도에 의존합니다.
이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 프로그래밍 언어를 컴퓨터가 실행할 수 있는 코드로 바꾸는 컴파일러의 속도 등에 달려있습니다.
하지만 우리는 이 시간을 대략적으로 추측할 수 있는 방법이 필요합니다. 그래서 표기법이 등장했습니다.
그럼 이 표기법은 어떻게 계산할까요? 수학적으로 생각한다면, 요소가 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의 속도가 걸리기 때문에 사용하지 않는 것과 같은 이유라고 보면 될 것 같습니다.
왜 빅오표기법을 사용할까? 부분에 '원할' 오타 있습니다ㅎㅎㅎ 글 잘 읽고가요!