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