복잡도(Complexity)와 빅오 표기법(Big-O Notation)

복잡도(Complexity)

 

알고리즘의 성능을 어떻게 평가할 수 있을까?

 

흔히 우리는 복잡도(Complexity)를 이용하여 알고리즘을 평가할 수 있다.

 

이 때 복잡도는 시간 복잡도와 공간 복잡도로 구성된다.

 

시간 복잡도: 알고리즘의 수행 시간 분석

공간 복잡도: 알고리즘의 메모리 사용량 분석

 

같은 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮을숙록 좋은 알고리즘이라고 할 수 있다.

(기업의 코딩 테스트에서도 요구사항(복잡도)를 고려해야 불미스러운 사고를 예방할 수 있다...)

 

 

빅오 표기법(Big-O Notation)

 

그렇다면 복잡도를 어떻게 구체적으로 표기할 수 있을까?

그 방법 중 하나는 바로 빅오 표기법(Big-O Notation)이다.

빅오 표기법은 가장 빠르게 증가하는 항만을 고려하는 표기법이다. (함수의 상한만을 나타냄)

 

예를 들어 5N^2 + 10N + 10000이라고 할 때 빅오 표기법은 O(N^2) 라고 표기할 수 있는 것이다.

 

아래는 빅오 표기법의 성능 비교이다.