[BigO] BigO 표기법

1. BigO표기법이란?

간단하게는 대략적으로 숫자를세는 것의 공식적인 표현이다.

다시말하면 입력된 내용이 늘어날 수록 알고리즘에 실행시간이 어떻게 변하는지 설명하는 공식적인 방식이다.

BigO표기법으로 함수의 입력값이 늘어나는것과 함수 실행시간이 변하는 관계를 숫자로 나타내고 이를 시각화 할수 있다.

N이 커질수록 컴퓨터가 f(n) 상수 곱하기 f(n) 보다 간단한 연산을 덜 해야한다면 그 알고리즘을 O(f(n))이라고 표현한다.

 

2. BigO 표기법의 필요성

모든 코드는 좋은 코드와 안좋은 코드로 분류할 수 없다.

그래서 우리는 이 애매한 표현들 대신에 숫자로 코드의 성능을 표기 할수 있다.

그것이 바로 BigO표기법이다.

 

3. 시간복잡도

O(1) : 상수의 계산, 변수 선언, 인덱스, 객체에서 키로 객체 찾기 등

O(n) : xy그래프로 그려보면 선형 직선이 나온다. for문과 같이 n번만큼 실행할때 실행시간도 그만큼 비례해서 늘어났을때를 의미한다.

O(n^2) : 이중 for문을 예로 들수 있다. xy그래프로 그려보면 횟수가 늘어날수록 실행시간이 x^2그래프와 비슷하게 늘어난다.

 

4. 공간복잡도

bool, 숫자, undefined, null은 자바스크립트에서 모두 불변 공간(O(1))이다.

그렇기 때문에 입력의 크기와 상관없이 똑같은 공간을 차지한다.

 

하지만 문자열(O(n))은 다르다.

refernece타입, 배열 객체도 대부분 O(n)이다.

n은 배열의 길이이거나 객체의 키 갯수일수도 있다. 

정확히 말하면 길이는 아니지만 길이가 4인 배열과 2인배열 중 길이가 4인배열이 2인배열보다 2배 더많은 공간을 차지한다.

 

로그함수(O(log n))은 O(n)보다 실행시간에서 보면 좋은 그래프를 가지고 있다.

어떤 탐색 알고리즘들은 로그시간 복잡도를 가진다. 그리고 효율적인 정렬 알고리즘들도 로그와 관련되어 있다.

모든 정렬 알고리즘들이 그런것은 아니지만 효율적인 것들이 그렇다.

재귀에서도 로그와 관련되어있고 시간복잡도가 아닌 공간복잡도와 관련되어 있다.

 

5. 정리

알고리즘의 성능을 분석하기 위해 BigO표기법을 이용한다.

입력의 크기가 늘어날수록 전체적인 추세와 관련되어 있다.

우리가 궁금한것은 실행시간이 어떻게 변하는지, 공간복잡도가 어떻게 변하는지 이다.

BigO를 통해서 시간과 공간복잡도에 대한 이해를 높일 수 있다.

정확도가 아니라 전체적인 추세를 중요하게 생각한다.

BigO로 측정되는 알고리즘의 시간과 공간 복잡도는 하드웨어에 영향을 받지 않는다.

어느 알고리즘을 일반컴퓨터와 슈퍼컴퓨터에서 실행하는 속도는 실제로 차이가 있겠지만 전박적인 주제는 다르지 않다.

왜냐하면 BigO는 실행될 연산의 갯수를 따지기 때문이다.