빅오표기법 - 시간복잡도

빅오 표기법이란?

알고리즘의 효율성을 예측하는 척도

ex) O(N), O(1), O(N제곱)

시간복잡도와 공간복잡도를 표현가능하다.

시간복잡도는 시간과 관련된 효율성을 말하는 것이고

공간복잡도는 메모리와 관련된 효율성을 말하는 것이다.

최근에 와서는 기술력에 따라 메모리 성능이 높아졌기 때문에

일반적으로 공간복잡도보단 시간복잡도를 고려한다.

아래는 복잡도 차트이다.

• 빅오 표기법 앞에 붙는 상수는 무시할 수있다.

왜냐하면 빅오 표기법은 n이 충분히 큰 값이라고 가정하기 때문에

연산에 큰 영향을 끼치지 않는다고 생각한다.

> 10 * O(n) = O(n)

시간 복잡도란?

시간복잡도는 정확한 시간이 아니라 처리 시간의 증가율을 나타내는 척도이다.

 

공간 복잡도란?