알고리즘 차수

차수(order)

차수란, 알고리즘에서는 복잡도를 표시하기 위해 사용하는 표기법으로 불린다.

• 선형시간(linear time)알고리즘: n, 100n
• 이차시간(quadratic time)알고리즘: n²,0.01n²

사실 선형시간 알고리즘은 어차피 n씩 증가하기 때문에 체감을 하지 못하지만 차수가 늘어나게 되면 그 경사, 급격도는 급하게 증가하게 된다.

Big O표기

Big O란 점근적 상한(Asymptotic Upper Bound)라고 한다.

일반적으로 O(n²)의 알고리즘을 설계했다는 뜻은 시간이 항상 n²이 걸린다는 것이 아닌 아무리 늦어도, 상한이 n²이라는 뜻이다.

이를 식으로 표현하면

n² + 10n + 9∈ O(n²) 으로 성립된다.
100n + 9 ∈ O(n²) 또한 성립하게 된다.

그렇다면 n³ ∈ O(n²) 성립이 가능하냐고 물어본다면 당연하게 불가능하다.