빅오 표기법 존재의 이유

이 소프트웨어의 규모가 커질까?
규모가 커질거라 예상이 된다면 확장성을 미리 갖춰야 한다는 뜻일것이다.

여기서 확장성(Scalability)이란, 아키텍처 입장에서는 앱을 쉽게 변경할 수 있음을 의미하고, 데이터베이스에서는 데이터를 저장하거나 검색하는데 걸리는 시간을 의미한다.

데이터의 양에 따라서 같은 알고리즘이라도 실행 시간과 메모리 사용량이 다르게 나타나는데 이것을 수량화 하는 기술이 Big O 표기법이다.

실행 시간과 메모리 사용은 각각 시간 복잡도와 공간 복잡도로 나타낼 수 있다.
시간과 공간 복잡도는 확장성 측정의 상위 척도이다. 복잡성의 형태를 나타내는 방법으로 빅오 표기법을 사용하는 것이지 실제 속도나 메모리 사용량을 측정하는 것이 아니다.

시간 복잡도(Time complexity)

데이터의 양에 따라 알고리즘을 실행하는 데 필요한 시간을 측정한다면 아래와 같이 그래프 축을 그려야 한다.

가로축인 Data는 데이터의 규모를 나타낸다.
세로축인 Time은 걸리는 시간을 나타낸다.

시간 복잡도를 나타낸다는 것은 데이터의 규모 대비 알고리즘 수행 시간을 나타낸다는 것이다.
그래서 아래 알고리즘들 모두 가로축은 모두 동일하게 그 기준을 제시하고 있으며, 시간축이 어떻게 변하는지에 따라 여러 알고리즘으로 그 특징을 나타낸다.

첫번째, Constant time. 일정한 시간이 걸리는 알고리즘이다.

두번째, Linear time 알고리즘. 데이터가 증가하는 만큼 시간도 증가하는 알고리즘이다.

세번째, Quadratic time. 이차 시간 알고리즘. n제곱으로 시간이 더 걸리게 되는 알고리즘이다.

네번째, Logarithmic time 알고리즘. 대수(log) 시간 알고리즘으로 데이터 증가에 따라 걸리는 시간이 증가량의 절반만큼만 더 필요하게되는 알고리즘이다. 데이터가 10 증가하면, 시간은 그 절반인 5 증가하고, 또 10 증가하면 5의 절반인 2.5만큼, 또 10 증가하면 1.25만큼 실행 시간이 늘어나게 된다.

다섯번째, Quasilinear time. 준선형 시간 알고리즘. 선형 시간 및 로그 시간의 곱이다.

그래프를 보면 정말 최악으로 보이는 알고리즘 같지만 뒤에 나올 더 나쁜 알고리즘에 비해서는 더 낫다고 한다.

기타 시간 복잡도
다항식 시간, 지수 시간, 계승 시간 등이 있다.


공간 복잡도(Space complexity)

공간 복잡도를 계산하기 위해 함수에 대한 메모리 할당을 분석한다.
정렬된 배열을 프린트 할 때, 배열을 통째로 복사하여 프린트한다면 O(n)이 되겠지만
데이터 양에 관계없이 몇가지 정해진 변수만 메모리에 할당하여 배열의 내용을 프린트하는 방법을 사용하면 O(1)이 된다.


기타 표기법
빅오 표기법 외에 빅 오메가, Big Theta 표기법도 있다.
빅 오메가는 알고리즘에 대한 최상의 실행 시간을 측정한다. 최사아의 경우를 얻는게 종종 불가능하므로 빅오만큼 유용하지 않다.
Big Theta 는 '최상의 경우와 나쁜 경우가 동일한' 알고리즘의 런타임을 측정하는데 사용된다.


확인 문제:
시간 복잡도의 알고리즘들을 비용순으로 정렬한다면?
상수 < 대수(log) < 선형 < 준선형 < 2차
위와 같이 정렬하더라도 작은 데이터 세트에서는 시간 복잡도는 별 관계가 없다. 순서가 뒤바뀔수도 있다는 것.