[알고리즘] 빅오(Big-O)표기법

알고리즘은 제한된 공간과 시간안에 데이터를 어떻게 처리할 것인지를 정의한 로직이다. 그럼 내가 짠 알고리즘이 효율적인지 어떻게 알 수 있을까? 알고리즘이 결과값을 도출하기까지의 속도를 측정하거나, 얼마만큼의 메모리를 잡아먹는지를 기준으로 알고리즘의 효율성을 평가할 수 있을 것이다. 알고리즘을 평가하는 지표에는 시간 복잡도와 공간 복잡도 가 있다.

• 시간 복잡도 : 어떤 알고리즘이 더 빠르고 느린지에 대한 속도를 다룸
• 공간 복잡도 : 메모리를 적게 쓰고 많이 쓰는 지에 대한 메모리 사용량을 다룸

최적의 알고리즘은 적은 메모리 사용과 빠른 속도를 모두 충족해야하나, 일반적으로는 속도를 기준으로 알고리즘을 평가되고, 이때 속도는 연산 횟수로 측정된다.

빅오 표기법은 동일한 알고리즘의 로직으로 인풋이 점점 쌓일 수록 시간이 얼마나 걸리는지를 알 수 있는 시간복잡도를 표기할 수 있는 방법이다. 그래서 알고리즘을 짤 때 input의 사이즈가 커질 수록 빅 오가 어떻게 변화하는지를 생각해야한다. 그리고 공간과 시간의 복잡도는 어떤지 어떤 자료구조를 이용하면 좋을지 생각해야됨

빅 오는 시간 단위가 아닌 알고리즘에 필요한 단계 수만을 고려함으로써 일관성을 유지한다.